Recruitment By [Lucky] Numbers

In the past few years I have interviewed a lot of people for various software development positions. Finding the right employee is always a challenge (as Franco DiAddezio put it, recruitment is an equivalent of finding the perfect spouse after just one or two dates). Candidates can have plenty of work experience, and you can fairly easily confirm whether or not they really known the technologies advertised in their resume. But are technology skills alone sufficient? My personal opinion is that a good software engineer is defined by his or her analytical thinking and problem-solving abilities. Specific technologies, such as programming languages and API's can always be learned.

My own litmus test for identifying the right engineer is a small but elegant programming problem called "The Lucky Numbers" problem. I first heard of it years ago in the university, and more recently - on Mikhail Gustokashin's site dedicated to programming problems where it is ranked "Very Easy" (follow the link only if you can read Russian). Here it is:

A 6-digit ticket number is considered "lucky" if the sum of its first 3 digits equals the sum of last 3 digits. For example, "006123" and "511304" are both lucky, "980357" isn't. Write an efficient algorithm to determine how many lucky numbers exists among all 6-digit numbers (from 000000 to 999999).

First, let's write an inefficient algorithm. We will iterate through all six-digit numbers and increment the counter if sum of first 3 equals to sum of last 3.

for(int i=0; i<10; i++)
for(int j=0; j<10; j++)
for(int k=0; k<10; k++)
for(int l=0; l<10; l++)
for(int m=0; m<10; m++)
for(int n=0; n<10; n++)
if(i+j+k == l+m+n) luckyNumbersCount++;

This algorithm performs 1 million iterations and it is the least I would expect from a candidate (amazingly, more than half failed to produce it). We can arrive at the efficient solution by carefully reading the problem. It doesn't ask us to produce all "lucky numbers", only their quantity. Can we find it without generating the numbers? We know that digit sums of both halves of the lucky number are equal. A sum of digits can take values from 0 (0+0+0) to 27 (9+9+9). For each value, we need to find out how many combinations of digits can produce it, e.g. "1" has 3 combinations: "001", "010", and "100". Evidently, there are 3 * 3 = 9 "lucky numbers" that correspond to the value of "1". So, here is optimized algorithm that performs only 1027 iterations:

int[] combinations = new int[28];
for(int i=0; i<10; i++)
for(int j=0; j<10; j++)
for(int k=0; k<10; k++)
combinations[i+j+k]++;

int luckyNumbersCount = 0;
for(int i=0; i<28; i++)
luckyNumbersCount += combinations[i] * combinations[i];