A friend of mine is interviewing for a job. One of the interview questions got me thinking, just wanted some feedback.
There are 2 non-negative integers: i and j. Given the following equation, find an (optimal) solution to iterate over i and j in such a way that the output is sorted.
2^i * 5^j
So the first few rounds would look like this:
2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25
Try as I might, I can't see a pattern. Your thoughts?
Dijkstra derives an eloquent solution in "A Discipline of Programming". He attributes the problem to Hamming. Here is my implementation of Dijkstra’s solution.