# Two numbers question

Tags: , | Posted by Admin on 5/10/2012 7:37 AM | Comments (1)

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? on 1/2/2013 2:51 PM One suggestion:

#include <map>

int g( uint a, uint b )
{
using namespace std;

// ordered storage
map< uint,pair<uint,uint> > heap;
// insert root element (a^0*b^0 = 1)
heap[ 1U ] = make_pair( 0U, 0U );

// run iterations
const uint N = 200U; uint n = 0U;
while ( n++ < N )
{
// pop minimum element from front
auto front = *heap.begin(); heap.erase( heap.begin() );

// ordered insert of new neighbour 1
uint newKey = front.first * a;
if ( !heap.count(newKey) ) // if not inserted yet
heap[ newKey ] = std::make_pair( front.second.first+1, front.second.second );

// ordered insert of new neighbour 2
newKey = front.first * b;
if ( !heap.count(newKey) ) // if not inserted yet
heap[ newKey ] = std::make_pair( front.second.first, front.second.second+1 );

// print current
std::cout << a << "^" << front.second.first << "*" << b << "^" << front.second.second << "=" << front.first << std::endl;
}

return 0;
}   