In a previous post I discussed a recent brain teaser I had come across:
Find a 10-digit number, where each digit represents the number of that ordinal number in the whole number. So, the first digit represents the number of 0's in the whole 10 digits. The second digit represents the number of 1's in the whole 10 digits. And so on. The first digit is not a 0.
As I promised at the end of the "brain only" post, we'll do better than simply finding an answer, we'll find all of them (with the aid of a computer).
Making the Problem Smaller
Without any thinking, there are 9 billion total choices. This is not only intractable for the human brain, but becomes difficult for a computer too. A 3 GHz processor in the most optimal case can only perform 3 billion operations per second but there is a lot of counting, lists to create, and otherwise to find a number which fits the criteria. To start, we write our number as
Since there are 10 digits in total and each of the digits represent a subcount of occurrences, the total number of occurrences can be represented as the sum:
Additionally, (for example) since each 3 contributes a value of 3 to the digit sum, we must also have
This second equation (which requires the first to make sense) limits our choices of digits a great deal:
The last four are obvious since (for example) . We can also say that . It is clearly no bigger than 2 but in the case that we'd also have meaning . Thus to brute force the problem we can choose digits 5 through 9 (5 digits in total) from the 32 different possible ways to make them 0 or 1.
Listing All Choices
Now for the fun part: programming (in Python). We now have 90,000 choices for our first 5 digits and 32 choices for our last 5 digits.
We can use Python's
range(10**4, 10**5) to represent the 5-digit
numbers between 10,000 and 99,999 (inclusive). For the 32 choices
for the last 5 digits, we use
To see it in action on a smaller set of data:
>>> import itertools >>> for pair in itertools.product((0, 1), repeat=2): ... print pair ... (0, 0) (0, 1) (1, 0) (1, 1)
When we ask for 5 repeated
copies of the tuple
(0, 1) we get 32 possible 5-tuples as expected:
>>> len(list(itertools.product((0, 1), repeat=5))) 32
Before we can iterate through all of our combinations, we need a way to check if a given number fits the criterion. To do that we implement
def fits_criterion(digit_list): for i in xrange(10): if digit_list.count(i) != digit_list[i]: return False return True
list of digits, so as we loop over all choices, we'll turn
them into lists.
Now we can use our accumulated tools, loop through all choices and print any matches
for first5 in xrange(10**4, 10**5): first5_list = map(int, str(first5)) for last5 in itertools.product((0, 1), repeat=5): digit_list = first5_list + list(last5) # last5 is a tuple if fits_criterion(digit_list): print digit_list
As luck would have it, the output is simply
[6, 2, 1, 0, 0, 0, 1, 0, 0, 0]
In other words, the only number which fits the criteria is the one we found with our brains alone:
This serves to make the interview question that much more difficult, since there is a unique solution.