Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
142 lines (109 sloc) 4.41 KB
---
title: Quantitative Interview Brain Teaser: Computer Assistance
date: 2014-09-28
author: Danny Hermes (dhermes@bossylobster.com)
tags: Brain Teaser, Combinatorics, Digit Counting, Interview Questions, itertools, Mathematics, Programming, Python
slug: quantitative-interview-brain-teaser
comments: true
github_slug: templated_content/2014-09-28-quantitative-interview-brain-teaser.template
---
In a [previous post](/2014/09/quantitative-brain-teaser-brain-only.html)
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
{{ get_katex("(9 \\cdot 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
{{ get_katex("n = d_0, d_1 d_2 d_3, d_4 d_5 d_6, d_7 d_8 d_9", blockquote=True) }}
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:
{{ get_katex("d_0 + d_1 + d_2 + d_3 + d_4 + d_5 + d_6 + d_7 + d_8 + d_9 = 10", blockquote=True) }}
Additionally, (for example) since each 3 contributes a value of 3 to the
digit sum, we must also have
{{ get_katex("d_1 + 2 d_2 + 3 d_3 + 4 d_4 + 5 d_5 + 6 d_6 + 7 d_7 + 8 d_8 + 9 d_9 = 10", blockquote=True) }}
This second equation (which requires the first to make sense) limits our
choices of digits a great deal:
{{ get_katex("0 \\leq d_5, d_6, d_7, d_8, d_9 \\leq 1", blockquote=True) }}
The last four are obvious since (for example)
{{ get_katex("2 \\cdot 6 > 10") }}.
We can also say that
{{ get_katex("d_5 < 2") }}.
It is clearly no bigger than 2 but in the case that
{{ get_katex("d_5 = 2") }}
we'd also have
{{ get_katex("d_2 > 0") }}
meaning
{{ get_katex("2 d_2 + 5 d_5 = 2 d_2 + 10 > 10") }}.
Thus to brute force the problem we can choose digits 5 through
9 (5 digits in total) from the 32 {{ get_katex("(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
{{ get_katex("(9 \\cdot 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:
```python
>>> 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:
```python
>>> len(list(itertools.product((0, 1), repeat=5)))
32
```
#### 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
```python
def fits_criterion(digit_list):
for i in xrange(10):
if digit_list.count(i) != digit_list[i]:
return False
return True
```
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
```python
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
```python
[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:
{{ get_katex("6,210,001,000", blockquote=True) }}
This serves to make the interview question that much more difficult,
since there is a unique solution.