algorithmoptimizationhamming-numberssmooth-numbers

# Tricky Google interview question

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?

Solution

• Dijkstra derives an eloquent solution in "A Discipline of Programming". He attributes the problem to Hamming. Here is my implementation of Dijkstra’s solution.

``````int main()
{
const int n = 20;       // Generate the first n numbers

std::vector<int> v(n);
v[0] = 1;

int i2 = 0;             // Index for 2
int i5 = 0;             // Index for 5

int x2 = 2 * v[i2];     // Next two candidates
int x5 = 5 * v[i5];

for (int i = 1; i != n; ++i)
{
int m = std::min(x2, x5);
std::cout << m << " ";
v[i] = m;

if (x2 == m)
{
++i2;
x2 = 2 * v[i2];
}
if (x5 == m)
{
++i5;
x5 = 5 * v[i5];
}
}

std::cout << std::endl;
return 0;
}
``````