Quantitative Interview Brain Teaser: Computer Assistance

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 (9⋅10​9​​) 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

n=d​0​​,d​1​​d​2​​d​3​​,d​4​​d​5​​d​6​​,d​7​​d​8​​d​9​​.

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:

d​0​​+d​1​​+d​2​​+d​3​​+d​4​​+d​5​​+d​6​​+d​7​​+d​8​​+d​9​​=10

Additionally, (for example) since each 3 contributes a value of 3 to the digit sum, we must also have

d​1​​+2d​2​​+3d​3​​+4d​4​​+5d​5​​+6d​6​​+7d​7​​+8d​8​​+9d​9​​=10

This second equation (which requires the first to make sense) limits our choices of digits a great deal:

0≤d​5​​,d​6​​,d​7​​,d​8​​,d​9​​≤1

The last four are obvious since (for example) 2⋅6>10. We can also say that d​5​​<2. It is clearly no bigger than 2 but in the case that d​5​​=2 we'd also have d​2​​>0 meaning 2d​2​​+5d​5​​=2d​2​​+10>10. Thus to brute force the problem we can choose digits 5 through 9 (5 digits in total) from the 32 (2​5​​) 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 (9⋅10​4​​) 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 itertools.product. 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)

view raw itertools_example.py hosted with ❤ by GitHub

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

view raw itertools_five_products.py hosted with ❤ by GitHub

---

Checking Candidates

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

view raw fits_criterion.py hosted with ❤ by GitHub

This takes a list of digits, so as we loop over all choices, we'll turn them into lists.

---

Exhaustive Search

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

view raw find_tuples_exhaustive.py hosted with ❤ by GitHub

As luck would have it, the output is simply

[6, 2, 1, 0, 0, 0, 1, 0, 0, 0]

view raw unique_solution.py hosted with ❤ by GitHub

In other words, the only number which fits the criteria is the one we found with our brains alone:

6,210,001,000

This serves to make the interview question that much more difficult, since there is a unique solution. About Bossy Lobster

Quantitative Brain Teaser: Brain Only

I've recently been working some atrophied mental muscles and came across a brain teaser that was pretty nifty:

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.

---

Example

If we shortened from 10 digits to 4 digit, the number

2,020

works since we have d​0​​=2 and two 0's (in the second and fourth slots), d​1​​=0 since the number has no 1's, d​2​​=2 since the number has two 2's (in the first and third slots) and d​3​​=0 since the number has no 3's.

---

Shorthand Notation

In order to refer to each digit, for search we name them all:

n=d​0​​,d​1​​d​2​​d​3​​,d​4​​d​5​​d​6​​,d​7​​d​8​​d​9​​.

We can see this in the above example when we refer to the digits in the four digit number

n=d​0​​,d​1​​d​2​​d​3​​.

---

A Practical Approach, Breaking Into Subproblems

Our search space is massive, and with only our wits, we need to quickly find a way to focus on a small space of possibilities. Since the first digit allows us to place a number of 0's we try to set it equal to values starting from the largest. By doing this we only have a little wiggle room to find the places which don't hold a zero.

---

First Case: d​0​​=9

In this case our only choice is

9,000,000,000

since we must have nine 0's. However since we have one 9, d​9​​=0 should not occur.

Thus we see none of our choices are possible when d​0​​=9.

---

Second Case: d​0​​=8

Here we must have eight 0's and d​8​​>0 so our possible solutions must look like

8,000,000,0∗0

But this leaves us with d​8​​=1 as our only choice since we can't place any more 8's. But now the presence of a 1 in

8,000,000,010

can't coexist with d​1​​=0 so we again see none of our choices are possible when d​0​​=8.

---

Third Case: d​0​​=7

Here we have seven 0's and know that d​7​​=1. It must be at least 1 since the first digit is a 7. It can't be 2 because the presence of another 7 would mean another digit (other than 0) would occur 7 times, which is impossible since there are only 10 total digits.

Since we know d​7​​=1 our possible solutions must look like

7,∗00,000,100

But again here we reach an impossible point. If we set d​1​​=1 then that digit would contradict itself since it is the second occurrence of 1. If d​1​​=2 it would contradict d​2​​=0 and so on for higher values. In addition, we have used all our digits, so can't increase the value of d​1​​ by placing more 1's in our number.

Thus we see none of our choices are possible when d​0​​=7.

---

Fourth Case: d​0​​=6

Here we have six 0's and must have d​6​​=1 since (as above), two different digits can't occur six times among 10 digits.

Also as before we can't have d​1​​=1 but now have some extra freedom (an extra digit which doesn't have to be 0) so consider the case d​1​​=2. This corresponds to an occurrence of the digit 2, hence we set d​2​​=1.

Now we have 4 non-zero digits along with six 0's to place:

6,210,001,000

Thus we have found a number which satisfies the criteria! The zero digits in the 3, 4, 5, 7, 8, and 9 places correspond to the absence of those digits. The non-zero digits in the 0, 1, 2, and 6 places also are the correct counts of each of those digits.

As a math nerd, I was still curious to know how to find every possible number that satisfies the criteria, but that task is too tedious to handle with the brain alone (or at least to be worth reading about when solved by hand). In my follow up to this, I'll show how a combination of smarts and programming can perform an exhaustive search in under 10 seconds. About Bossy Lobster