Google Interview Question Software Engineer / Developers
I think there is a tricky way. Let 5 = 2^x, where x ~= 2.2 (I didn't solve it by computer. We say it is x = 2.2).
Therefore, 2^i*5^j = 2^i * (2^2.2)^j = 2^(i+2.2j). The problem can be reduced: increase i, j to sort the outputs. Then, it will become an "counting problem."
j=0, outputs are 1, 2, 3, 4, 5, 6, 7, 8, 9......
j=1, outputs are 2.2, 3.2, 4.2, 5.2, .....
j=2, outputs are 4.4, 5.4, 6.4, 7.4, .....
.
.
.
Tackling the sorting problem like this will be easier since it has a regular pattern (the incremental is 1 for each of j's).
You are welcome to comment on it. Thank you.
above sequence is arbit....i thnk once i or j is incrmented it cant b decremnted...we hv to keeep on incrmntng it.....othrwise give me a soln i m getng no idea
@mm: learn FIRST how to type first, before go for job hunting. What you mean by "arbit" ? Don't you know the spelling of "decremented" or "incrmntng"? Get lost!
For others: there exists O(n) solution for this problem, first proposed by Dijstra. It's a variation of "Ugly Number" that generates sequence of the form 2^i 3^j 5^k.
An interesting problem, which looks simple, but has deep root in number theory and applications in various fields. en.wikipedia.org/wiki/Regular_number
/* Shortest way to arrange in sorted order */
int i=0, j=0, x=0, count;
for(count=1;count<=20;count++)
{
printf("%d",(pow(2,x)*pow(5,j)));
if(x==0 || x==1)
{ x=++i;j=0; }
else
{ x-=2; j++ }
}
How did you arrive at this algorithm? I ran your code and it worked, but I still couldn't figure out a pattern. The only thing I noticed was the exponent for the second term (5) alternates between 0 and 1...the exponent for the first term (2) seems a little arbitrary.
Well Here is the Running Code But Until & Unless You Will Vist Above Blog it won't make you more clear.
#include<stdio.h>
#include<iostream>
using namespace std;
#define k 20 //modify it
int Lucky[k], ptr2, ptr5;
int minimum(int x,int y)
{
if (x<y) return x;
return y;
}
int nextLucky(int num)
{
int num2,num5;
if(num==0)
{
Lucky[num]=1;
ptr2=ptr5=0;
return Lucky[num];
}
num2=Lucky[ptr2]*2;
num5=Lucky[ptr5]*5;
Lucky[num]=minimum(num2,num5);
if(Lucky[num]==num2) ptr2++;
if(Lucky[num]==num5) ptr5++;
return Lucky[num];
}
int main()
{
int i;
for(i=0; i<k; i++)
printf("Lucky number no. %d is %d\n", i+1,nextLucky(i));
}
WgpShashank
minHeap.insert(1);
while(1)
{
minHeap.getMin(min);
print(min);
minHeap.add(min*2);
minHeap.add(min*5);
}
print the first 4 elements
cout <<2^0, 2^1, 2^2, 5^1
int nextI = 2, nextJ = 1;
int printedTillNow = 4;
while ( printedTillNow < n) {
nextI++;
if( Pow(2,nextI) > Pow(5,nextJ) {
nextJ++;
}
int j = 0;
for ( int i = nextI; i>=0; i-=2) {
cout<< Pow(2,i)*Pow(5,j);
printedTillNow++;
j++;
if(j > nextJ) {
j = 0;
}
}
}
int main()
{
// Generate the first n numbers
const int n = 20;
std::vector<int> v(n);
v[0] = 1;
int i2 = 0; // Index for 2
int i5 = 0; // Index for 5
// Next two candidates
int x2 = 2 * v[i2];
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;
}
Before posting a question, atleast UNDERSTAND it first. Your output should be something like (first 20):
- anonymous May 25, 20111
2
4
5
8
10
16
20
25
32
40
50
64
80
100
125
128
160
200
250