Tricky Google interview question

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?

Crassus

The optimal algorithm in terms of programmer time is to generate with two nested loops, then sort. Why do they ask questions like this? – Zoan

You may be able to determine transition points by looking at which number is greater. 2^2 < 5 but 2^3 > 5 so at that point you increase j. I think you can produce the output in O(n) rather than O(nlgn). @tom-zynch two nested loops is O(n^2). This question is very valid – Brom

@Mikhail, you have to generate ij numbers no matter what you do. The difference is between some specialized algorithm that might sort in O(ij) or a general sort in O(ij log(ij)). – Zoan

There's only one output, so optimal solution is O(n). Read my solution below – Brom

A similar question has been addressed before apparently: https://mcmap.net/q/144879/-nᵗʰ-ugly-number. – Swampland

@Tom Zych What would be the bounds of your loops? Say we want to let the exponents be any positive integer. Would you just loop forever? Also, the only reason my algorithm needs to compute all the i,j pairs is for output. – Joappa

Mmm, I see I had misread the question. I thought we were starting out with initial upper bounds i and j. So yes, we need another way. – Zoan

... and the OP should probably choose an answer already. After all, he's already got plenty of good ones. – Selfrising

there is a pattern, if you look at the problem as an i*j matrix. – Che

Out of curiosity what was the job position for? – Pleomorphism

Software engineer at Google. It was only the phone screen too. Seems pretty rough to me. – Crassus

A question like this better be for a company like Google. Any ordinary company that gave questions like this couldn't afford to hire the candidates that are good enough to answer this in the pressure and time constraints of an interview. Or wouldn't get interviewees that good in the first place. – Dissever

Answer 1

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;
}

Waylan

Relevant link: en.wikipedia.org/wiki/Regular_number#Algorithms. I don't think this is a very good interview question by the way. Here is a (handwritten paper) by Dijkstra where he provides and proves an algorithm for this problem: cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF – Rafflesia

When the goal is "to iterate over i and j" you need less storage capacity, a FIFO is enough. See my Python solution. – Geminian

When the goal is "to iterate over i and j", it is not the same problem. – Versicular

This is a really nice implementation, using a minimum of memory. It is linear memory even if you want only one number though. – Sparrow

@Andrey There are different version of this problem. Some start at 1, others at the smallest prime (2 here). My solution is a solution to the latter type of problem. Your second complain is simply wrong. Try to copy and paste my code and you will see that there are no duplicates. – Waylan

wow, nice, I particularly like how we avoid printing out 10 twice, i.e. once for 2*5 and once for 5*2 by having 2 separate if statements so we increment both of the counters – Isolation

@ThomasAhle Don't know if you saw this but it has code at the end that is capable of calculating n-th number in isolation. Like e.g. a billionth number. – Attainder

Answer 2

here is a more refined way of doing it (more refined than my previous answer, that is):

imagine the numbers are placed in a matrix:

     0    1    2    3    4    5   -- this is i
----------------------------------------------
0|   1    2    4    8   16   32
1|   5   10   20   40   80  160
2|  25   50  100  200  400  800
3| 125  250  500 1000 2000 ...
4| 625 1250 2500 5000 ...
j on the vertical

what you need to do is 'walk' this matrix, starting at (0,0). You also need to keep track of what your possible next moves are. When you start at (0,0) you only have two options: either (0,1) or (1,0): since the value of (0,1) is smaller, you choose that. then do the same for your next choice (0,2) or (1,0). So far, you have the following list: 1, 2, 4. Your next move is (1,0) since the value there is smaller than (0,3). However, you now have three choices for your next move: either (0,3), or (1,1), or (2,0).

You don't need the matrix to get the list, but you do need to keep track of all your choices (i.e. when you get to 125+, you will have 4 choices).

Gamp

I voted this up because I was thinking along the same lines, but in the general case, wouldn't this be something like O(i^2 * j)? You'd have to check several numbers for each number you output. – Zoan

@Tom you do have to check more than one number, but it's not that bad: when you output numbers between 125 and 625, you need to look at 4 values. between 625 and 3025, you look at 5 values. so really, it's j checks for every 1 output – Gamp

+1: Combine with this question: https://mcmap.net/q/144882/-selection-algorithms-on-sorted-matrix and looks like we have an O(n) solution. – Swampland

@Moron darn, I don't want to pay $25 for that algorithm, but it does look interesting. – Gamp

I don't think I could have figured it our without the matrix. Thanks! – Sanasanabria

@Sanasanabria that's how I figured it out, too :) – Gamp

Can this still be termed "iteration"? – Mccreary

actually, j ~ n^0.5 for n-th value in a sequence, since n values fill up an area on i x j plane. So this algo is O(n^1.5) time, with O(n^0.5) space. But there exists a linear time algo with same space complxty of n^0.5, and the mini-heap algo from the answer below is O(n*log(n)) time with same n^0.5 space. – Attainder

Answer 3

Use a Min-heap.

Put 1.

extract-Min. Say you get x.

Push 2x and 5x into the heap.

Repeat.

Instead of storing x = 2^i * 5^j, you can store (i,j) and use a custom compare function.

Swampland

A heap would give lg n time on its operations, which pushes the complexity to n lg n. – Vise

@glow: Yes, I don't see any O(n) solutions posted so far, though :-) – Swampland

@abel: That comment is old :-) Seems like he will have problems going from (1,1) to (4,0) too. But viewing it as a young's matrix (see vlad's answer) actually does allow an O(n) time algorithm. – Swampland

@Moron: I don't think there's anything wrong with that solution. Certainly nothing wrong in the first 30 elements, which I just checked right now (that would cover the (1,1) -> (4,0) case). – Selfrising

@abel: Yeah didn't actually try to run it :-) Maybe there is an easy proof of its correctness too. FWIW, it already has my +1. – Swampland

@Moron: someone else provided a link to an EWD that deals with essentially the same problem. The nice thing is that it generalizes to any number of primes. – Selfrising

@abel: I looked at EWD's paper, and it is quite cryptic, with all the attempts at being formal. btw, if you look at the other link in that comment, there is a claim on the wiki page that imperative solutions are non-trivial... – Swampland

@Moron: I agree, but hey, that's the downside of having rigorous proofs ;) – Selfrising

@abel: Not really. We can have rigorous proofs without actually drowning the reader in a flood of symbols :-) It must have been written at a time when EWD was into computer verification etc (which I guess is always :-)) – Swampland

@Moron, I believe I have posted a O(n) solution. Please check to make sure that it works though at the specified speed. – Joappa

@KLee: Do you have a proof of the 'notice that...', it seems very similar to abel's observation. – Swampland

This solution is O(n*log(n)) run time. Vlad's version is O(n^1.5). Dijkstra's is O(n), to produce n numbers in the sequence. All with O(n^0.5) space complxty. – Attainder

@WillNess: this solution has a linear space complexity, not n^0.5 – Evoke

@EyalSchneider have you missed the "extract-Min" part? – Attainder

@WillNess: If I understand the algorithm correctly, on each iteration it removes an item from the heap and then adds two. That means linear increase in the heap size. – Evoke

@EyalSchneider no, sometimes it removes two of them. 10 is a multiple of both 2 and 5, e.g. – Attainder

@WillNess: Now I realize that the candidate set at any moment is on the top edge of the grid ixj, so it looks reasonable that the edge size is O(sqrt(N)), where N is the total number of cells that have been added. However, this requires a proof. I can't find one easily. It really depends on the shape of the edge. – Evoke

@EyalSchneider the shape of the edge is a thick diagonal straight line around a target log value. Check out my answers in the tags hamming-numbers and smooth-numbers; also RosettaCode; and WP of course. I once proved mathematically (on a piece of paper, don't remember now) the n^2/3 size for the same algorithm for {2,3,5}-smooth numbers. I think I just used the estimate formula from WP, and thought up estimates for the back-pointers; but I don't remember the details. – Attainder

Answer 4

A FIFO-based solution needs less storage capacity. Python code.

F = [[1, 0, 0]]             # FIFO [value, i, j]
i2 = -1; n2 = n5 = None     # indices, nexts
for i in range(1000):       # print the first 1000
    last = F[-1][:]
    print "%3d. %21d = 2^%d * 5^%d" % tuple([i] + last)
    if n2 <= last: i2 += 1; n2 = F[i2][:]; n2[0] *= 2; n2[1] += 1
    if n5 <= last: i2 -= 1; n5 = F.pop(0); n5[0] *= 5; n5[2] += 1
    F.append(min(n2, n5))

output:

  0.                     1 = 2^0 * 5^0
  1.                     2 = 2^1 * 5^0
  2.                     4 = 2^2 * 5^0
 ...
998. 100000000000000000000 = 2^20 * 5^20
999. 102400000000000000000 = 2^27 * 5^17

Geminian

Answer 5

This is very easy to do O(n) in functional languages. The list l of 2^i*5^j numbers can be simply defined as 1 and then 2*l and 5*l merged. Here is how it looks in Haskell:

merge :: [Integer] -> [Integer] -> [Integer]
merge (a:as) (b:bs)   
  | a < b   = a : (merge as (b:bs))
  | a == b  = a : (merge as bs)
  | b > a   = b : (merge (a:as) bs)

xs :: [Integer]
xs = 1 : merge (map(2*)xs) (map(5*)xs)

The merge function gives you a new value in constant time. So does map and hence so does l.

Sparrow

I think that 'k' is not defined – Nelsen

let's just call this "merge" function union instead, as it is removing the duplicates. merge, as a part of mergesort, must preserve duplicates coming from both its input sequences. See Data.List.Ordered package for related stuff. – Attainder

+1 for Data.List.Ordered.union. That makes it one line: xs = 1 : union (map (2*) xs) (map (5*) xs) – Shrink

@Geminian Yes, it includes five times the list [1, 2, 4, 5,...] so it includes 5*4. – Sparrow

@Shrink Yes, this is the Data.List.Ordered.union function. Not to be confused with Data.List.union. – Sparrow

Answer 6

You have to keep track of the individual exponents of them, and what their sums would be

so you start with f(0,0) --> 1 now you have to increment one of them:

f(1,0) = 2
f(0,1) = 5

so we know 2 is the next - we also know we can increment i's exponent up until the sum surpases 5.

You keep going back and forth like this until you're at your deisred number of rounds.

Vise

Yes it is. You do one O(1) operation for each round. Sometimes you do the round early, but when you get to that round you don't have to do it there, so it works itself out. – Vise

How do you go from (1,1) to (4,0)? Please elaborate exactly what your algorithm is. – Swampland

The problem is, you don't just have two incremental possibilities -- e.g., you aren't done with f(*,2) just because you found that f(a1,b+1)>f(a2,b). An incremental approach will eventually generate an unbounded number of pairs neighboring the region you've already output. – Preponderate

@Waylan provided an implementation that was more than I could do on my lunch break, but that's what I was trying to get at. – Vise

Answer 7

Using dynamic programming you can do this in O(n). Ground truth is that no values of i and j can give us 0, and to get 1 both values must be 0;

TwoCount[1] = 0
FiveCount[1] = 0

// function returns two values i, and j
FindIJ(x) {
    if (TwoCount[x / 2]) {
        i = TwoCount[x / 2] + 1
        j = FiveCount[x / 2]
    }
    else if (FiveCount[x / 5]) {
        i = TwoCount[x / 2]
        j = FiveCount[x / 5] + 1
    }
}

Whenever you call this function check if i and j are set, if they are not null, then populate TwoCount and FiveCount

---

C++ answer. Sorry for bad coding style, but i'm in a hurry :(

#include <cstdlib>
#include <iostream>
#include <vector>

int * TwoCount;
int * FiveCount;

using namespace std;

void FindIJ(int x, int &i, int &j) {
        if (x % 2 == 0 && TwoCount[x / 2] > -1) {
                cout << "There's a solution for " << (x/2) << endl;
                i = TwoCount[x / 2] + 1;
                j = FiveCount[x / 2];
        } else if (x % 5 == 0 && TwoCount[x / 5] > -1) {
                cout << "There's a solution for " << (x/5) << endl;
                i = TwoCount[x / 5];
                j = FiveCount[x / 5] + 1;
        }    
}

int main() {
        TwoCount = new int[200];
        FiveCount = new int[200];

        for (int i = 0; i < 200; ++i) {
                TwoCount[i] = -1;
                FiveCount[i] = -1;
        }

        TwoCount[1] = 0;
        FiveCount[1] = 0;

        for (int output = 2; output < 100; output++) {
                int i = -1;
                int j = -1;
                FindIJ(output, i, j);
                if (i > -1 && j > -1) {
                        cout << "2^" << i << " * " << "5^" 
                                     << j << " = " << output << endl;
                        TwoCount[output] = i;
                        FiveCount[output] = j;
                }
        }    
}

Obviously you can use data structures other than array to dynamically increase your storage etc. This is just a sketch to prove that it works.

Brom

This looks like an interesting answer, but I fail to see how it really works. Could you add more details ? – Groomsman

After studying it myself, I really don't see how it works. Assuming integer division, it'll give exactly the same result for 3 as for 2. Moreover, if the if conditions are tests for non-zero, it will never work, as there are no non-zero entries. – Jehial

Posted a C++ version for all you nay sayers. @David Your comments are correct, but my original code was pseudo code and I was thinking in scripting terms, so not-integer division and distinguishing between null entry and entry of value 0 – Brom

this code enumerates all natural numbers, so, per comment of @ThomasAhle to the answer by "Lost in Alabama" below, it takes O(exp(sqrt(n))), to produce n numbers of the sequence. Linear algorithm exists, e.g. as given by ThomasAhle. – Attainder

You're right. In my understanding O(n) meant n being the last value, not number of printed items, which isn't correct. I don't know how functional languages work, or how merge works in constant time, but his answer got my upvote – Brom

Answer 8

Why not try looking at this from the other direction. Use a counter to test the possible answers against the original formula. Sorry for the pseudo code.

for x = 1 to n
{
  i=j=0
  y=x
  while ( y > 1 )
  {
    z=y
    if y divisible by 2 then increment i and divide y by 2
    if y divisible by 5 then increment j and divide y by 5

    if y=1 then print i,j & x  // done calculating for this x

    if z=y then exit while loop  // didn't divide anything this loop and this x is no good 
  }
}

Eslinger

This runs in about O(4^sqrt(n)) because the nth number of the sequence is of approximately that size. – Sparrow

Answer 9

This is the relevant entry at OEIS.

It seems to be possible to obtain the ordered sequence by generating the first few terms, say

1 2 4 5

and then, starting from the second term, multiplying by 4 and 5 to get the next two

1 2 4 5 8 10

1 2 4 5 8 10 16 20

1 2 4 5 8 10 16 20 25

and so on...

Intuitively, this seems correct, but of course a proof is missing.

Selfrising

Wrong :( [1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 625 ] However 500 < 512 = 2^9 < 625. – Geminian

@NateKerkhofs, 512 is generated but it is out of order as 512 is less than the already generated 625; the algorithm would need further logic to put the output in order - Thus the algorithm is not as simple as proposed and not the same algorithm at all. – Jeana

Answer 10

You know that log_2(5)=2.32. From this we note that 2^2 < 5 and 2^3 > 5.

Now look a matrix of possible answers:

j/i  0   1   2   3   4   5
 0   1   2   4   8  16  32
 1   5  10  20  40  80 160 
 2  25  50 100 200 400 800
 3 125 250 500 ...

Now, for this example, choose the numbers in order. There ordering would be:

j/i  0   1   2   3   4   5
 0   1   2   3   5   7  10
 1   4   6   8  11  14  18
 2   9  12  15  19  23  27
 3  16  20  24...

Note that every row starts 2 columns behind the row starting it. For instance, i=0 j=1 comes directly after i=2 j=0.

An algorithm we can derive from this pattern is therefore (assume j>i):

int i = 2;
int j = 5;
int k;
int m;

int space = (int)(log((float)j)/log((float)i));
for(k = 0; k < space*10; k++)
{
    for(m = 0; m < 10; m++)
    {
        int newi = k-space*m;
        if(newi < 0)
            break;
        else if(newi > 10)
            continue;
        int result = pow((float)i,newi) * pow((float)j,m);
        printf("%d^%d * %d^%d = %d\n", i, newi, j, m, result);
    }
}   

NOTE: The code here caps the values of the exponents of i and j to be less than 10. You could easily extend this algorithm to fit into any other arbitrary bounds.

NOTE: The running time for this algorithm is O(n) for the first n answers.

NOTE: The space complexity for this algorithm is O(1)

Joappa

You wrote "every row starts 2 columns behind the row starting it". However 2^9=512 and 5^4=625, so this is not true for row 4. – Geminian

@user678105 You are right. This code does not work. Sorry all. This code doesn't work because of the round off of the log and my assumption that it didn't matter. – Joappa

Here's how you fix this. On the (x,y) plane full of points with integral coefficients, draw a line from (0,1) to (log2(5),0). (0,0) is in the top left corner. X axis goes to the right, Y axis goes down. Now draw a line from the (0,0) origin point which is perpendicular to the 1st line. Now slide the first line along the second, further and further away from origin, and collect the integer-coordinates points as they are crossed over. For {2,3,5}-generated sequence, it'll be a plane moving across, in (i,j,k) space. If you can translate this idea into code, give me a shout-out. :) – Attainder

Answer 11

My implementation is based on the following ideas:

• Use two queues Q2 and Q5, both initialized with 1. We will keep both queue in sorted order.
• At every step, dequeue the smallest number element MIN from Q2 or Q5 and print it. If both Q2 and Q5 have the same element - remove both. Print this number. This is basically merging of two sorted arrays - at each step choose the smallest element and advance.
• Enqueue MIN*2 to Q2 and MIN*5 to Q5. This change does not break the invariant of Q2/Q5 being sorted, because MIN is higher than previous MIN number.

Example:

Start with 1 and 1 (to handle i=0;j=0 case):
  Q2: 1
  Q5: 1
Dequeue 1, print it and enqueue 1*2 and 1*5:
  Q2: 2
  Q5: 5
Pick 2 and add 2*2 and 2*5:
  Q2: 4
  Q5: 5 10
Pick 4 and add 4*2 and 4*5:
  Q2: 8
  Q5: 5 10 20
....

Code in Java:

public void printNumbers(int n) {
    Queue<Integer> q2 = new LinkedList<Integer>();
    Queue<Integer> q5 = new LinkedList<Integer>();
    q2.add(1);
    q5.add(1);
    for (int i = 0; i < n; i++) {
        int a = q2.peek();
        int b = q5.peek();
        int min = Math.min(a, b);
        System.out.println(min);
        if (min == a) {
            q2.remove();
        }
        if (min == b) {
            q5.remove();
        }
        q2.add(min * 2);
        q5.add(min * 5);
    }
}

Sayed

Answer 12

calculate the results and put them in a sorted list, together with the values for i and j

Gamp

That'll probably give you holes in the later end of your sequence. E.g. you'll have 2^n*5^n but not 2^(n+1)*5^(n-1) which is smaller. – Sparrow

@Thomas I'm not sure I follow your logic here. If you calculate one, why would you not also calculate the other? – Gamp

@Gamp You need to have a limit on your i's and j's, don't you? Otherwise you'll never get to the sorting state, and hence you'll never return a single value. But for any limit n you choose, your list will be flawed. – Sparrow

@Thomas your argument still doesn't make sense. The OP never specified an end to his list of results. If he does, you can find the max i and j. – Gamp

@Gamp As I read your answer, you first calculate the "results" / the 2^i*5^j values, and then sort them. If you don't have a limited number of "results", how will you ever get to the sorting step? – Sparrow

@Thomas I was originally thinking that you can put the results in the list as they are generated, but it doesn't really matter. Since the OP didn't specify the end condition for the results list, I didn't specify the end condition for the algorithm either. – Gamp

and what @ThomasAhle is saying, is that as you put them in, there will always be holes near the end of your sequence, at each point in time. You must specify the boundary up to which the sequence has no holes, at each point in time; otherwise you can't use it at all, at each point in time, as you don't know whether you'll miss some numbers or not. Without addressing this problem your procedure is unusable. – Attainder

Answer 13

The algorithm implemented by user515430 by Edsger Dijkstra (http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF) is probably as fast as you can get. I call every number that is a form of 2^i * 5^j a "special number". Now vlads answer would be O(i*j) but with a double algorithm, one to generate the special numbers O(i*j) and one to sort them (according to the linked article also O(i*j).

But let's check Dijkstra's algorithm (see below). In this case n is the amount of special numbers we are generating, so equal to i*j. We are looping once, 1 -> n and in every loop we perform a constant action. So this algorithm is also O(i*j). And with a pretty blazing fast constant too.

My implementation in C++ with GMP (C++ wrapper), and dependancy on boost::lexical_cast, though that can be easily remove (I'm lazy, and who doesn't use Boost?). Compiled with g++ -O3 test.cpp -lgmpxx -o test. On Q6600 Ubuntu 10.10 time ./test 1000000 gives 1145ms.

#include <iostream>
#include <boost/lexical_cast.hpp>
#include <gmpxx.h>

int main(int argc, char *argv[]) {
    mpz_class m, x2, x5, *array, r;
    long n, i, i2, i5;

    if (argc < 2) return 1;

    n = boost::lexical_cast<long>(argv[1]);

    array = new mpz_class[n];
    array[0] = 1;

    x2 = 2;
    x5 = 5;
    i2 = i5 = 0;

    for (i = 1; i != n; ++i) {
        m = std::min(x2, x5);

        array[i] = m;

        if (x2 == m) {
            ++i2;
            x2 = 2 * array[i2];
        }

        if (x5 == m) {
            ++i5;
            x5 = 5 * array[i5];
        }
    }

    delete [] array;
    std::cout << m << std::endl;

    return 0;
}

Guiltless

Answer 14

If you draw a matrix with i as the row and j as the column you can see the pattern. Start with i = 0 and then just traverse the matrix by going up 2 rows and right 1 column until you reach the top of the matrix (j >= 0). Then go i + 1, etc...

So for i = 7 you travel like this:

7, 0 -> 5, 1 -> 3, 2 -> 1, 3

And for i = 8:

8, 0 -> 6, 1 -> 4, 2 -> 2, 3 -> 0, 4

Here it is in Java going up to i = 9. It prints the matrix position (i, j) and the value.

for(int k = 0; k < 10; k++) {

    int j = 0;

    for(int i = k; i >= 0; i -= 2) {

        int value = (int)(Math.pow(2, i) * Math.pow(5, j));
        System.out.println(i + ", " + j + " -> " + value);
        j++;
    }
}

Rockbound

Answer 15

My Intuition :

If I take initial value as 1 where i=0, j=0, then I can create next numbers as (2^1)(5^0), (2^2)(5^0), (2^0)*(5^1), ... i.e 2,4,5 ..

Let say at any point my number is x. then I can create next numbers in the following ways :

• x * 2
• x * 4
• x * 5

Explanation :

Since new numbers can only be the product with 2 or 5.
But 4 (pow(2,2)) is smaller than 5, and also we have to generate 
Numbers in sorted order.Therefore we will consider next numbers
be multiplied with 2,4,5.
Why we have taken x*4 ? Reason is to pace up i, such that it should not 
be greater than pace of j(which is 5 to power). It means I will 
multiply my number by 2, then by 4(since 4 < 5), and then by 5 
to get the next three numbers in sorted order.

Test Run

We need to take an Array-list of Integers, let say Arr.

Also put our elements in Array List<Integers> Arr.
Initially it contains Arr : [1]

• Lets start with x = 1.

  Next three numbers are 1*2, 1*4, 1*5 [2,4,5]; Arr[1,2,4,5]

• Now x = 2

  Next three numbers are [4,8,10] {Since 4 already occurred we will ignore it} [8,10]; Arr[1,2,4,5,8,10]

• Now x =4

  Next three numbers [8,16,20] {8 already occurred ignore it} [16,20] Arr[1,2,4,5,8,10,16,20]

• x = 5

  Next three numbers [10,20,25] {10,20} already so [25] is added Arr[1,2,4,5,8,10,16,20,25]

Termination Condition

 Terminating condition when Arr last number becomes greater 
 than (5^m1 * 2^m2), where m1,m2 are given by user.

Analysis

 Time Complexity : O(K) : where k is numbers possible between i,j=0 to 
 i=m1,j=m2.
 Space Complexity : O(K)

Timi

Answer 16

Just was curious what to expect next week and have found this question.

I think, the idea is 2^i increases not in that big steps as 5^j. So increase i as long as next j-step wouldn't be bigger.

The example in C++ (Qt is optional):

QFile f("out.txt"); //use output method of your choice here
f.open(QIODevice::WriteOnly);
QTextStream ts(&f);

int i=0;
int res=0;
for( int j=0; j<10; ++j )
{
    int powI = std::pow(2.0,i );
    int powJ = std::pow(5.0,j );
    while ( powI <= powJ  ) 
    {
        res = powI * powJ;
        if ( res<0 ) 
            break; //integer range overflow

        ts<<i<<"\t"<<j<<"\t"<<res<<"\n";
        ++i;
        powI = std::pow(2.0,i );

    }
}

The output:

i   j   2^i * 5^j
0   0   1
1   1   10
2   1   20
3   2   200
4   2   400
5   3   4000
6   3   8000
7   4   80000
8   4   160000
9   4   320000
10  5   3200000
11  5   6400000
12  6   64000000
13  6   128000000
14  7   1280000000

Langham

This solution misses some combinations. For example, it doesnt examine the case where i=1,j=2 any case where i=1 and j>1 for that matter.. – Tonometer

@Federico: You are right! No wonder why I've failed google-interviews twice with 6 years interval but nearly the same questions :-) – Langham

Answer 17

Here is my solution

#include <stdio.h>
#include <math.h>
#define N_VALUE 5
#define M_VALUE  5

int n_val_at_m_level[M_VALUE];

int print_lower_level_val(long double val_of_higher_level, int m_level)
{
int  n;
long double my_val;


for( n = n_val_at_m_level[m_level]; n <= N_VALUE; n++) {
    my_val =  powl(2,n) * powl(5,m_level);
    if(m_level != M_VALUE && my_val > val_of_higher_level) {
        n_val_at_m_level[m_level] = n;
        return 0;
    }
    if( m_level != 0) {
        print_lower_level_val(my_val, m_level - 1);
    }
    if(my_val < val_of_higher_level || m_level == M_VALUE) {
        printf("    %Lf n=%d m = %d\n", my_val, n, m_level);
    } else {
        n_val_at_m_level[m_level] = n;
        return 0;
    }
 }
 n_val_at_m_level[m_level] = n;
 return 0;
 }


 main()
 {
    print_lower_level_val(0, M_VALUE); /* to sort 2^n * 5^m */
 }

Result :

1.000000 n = 0 m = 0
2.000000 n = 1 m = 0
4.000000 n = 2 m = 0
5.000000 n = 0 m = 1
8.000000 n = 3 m = 0
10.000000 n = 1 m = 1
16.000000 n = 4 m = 0
20.000000 n = 2 m = 1
25.000000 n = 0 m = 2
32.000000 n = 5 m = 0
40.000000 n = 3 m = 1
50.000000 n = 1 m = 2
80.000000 n = 4 m = 1
100.000000 n = 2 m = 2
125.000000 n = 0 m = 3
160.000000 n = 5 m = 1
200.000000 n = 3 m = 2
250.000000 n = 1 m = 3
400.000000 n = 4 m = 2
500.000000 n = 2 m = 3
625.000000 n = 0 m = 4
800.000000 n = 5 m = 2
1000.000000 n = 3 m = 3
1250.000000 n = 1 m = 4
2000.000000 n = 4 m = 3
2500.000000 n = 2 m = 4
3125.000000 n = 0 m = 5
4000.000000 n = 5 m = 3
5000.000000 n = 3 m = 4
6250.000000 n = 1 m = 5
10000.000000 n = 4 m = 4
12500.000000 n = 2 m = 5
20000.000000 n = 5 m = 4
25000.000000 n = 3 m = 5
50000.000000 n = 4 m = 5
100000.000000 n = 5 m = 5

Kopeck

Answer 18

I know I am likely wrong but there is a very simple heuristic here since it does not involve many numbers like 2,3,5. We know that for any i,j 2^i * 5^j next sequence would be 2^(i-2) * 5^(j+1). Being a google q it must have a simple solution.

def func(i, j):
 print i, j, (2**i)*(5**j)

imax=i=2
j=0
print "i", "j", "(2**i)*(5**j)"

for k in range(20):
    func(i,j)
    j=j+1; i=i-2
    if(i<0):
        i = imax = imax+1
        j=0

This produces output as :

i j (2**i)*(5**j)
2 0 4
0 1 5
3 0 8
1 1 10
4 0 16
2 1 20
0 2 25
5 0 32
3 1 40
1 2 50
6 0 64
4 1 80
2 2 100
0 3 125
7 0 128
5 1 160
3 2 200
1 3 250
8 0 256
6 1 320

Acceptor

it might work up to 20, or 200, but at some point it'll start skipping some numbers and/or output them in wrong order. – Attainder

Answer 19

If you go by what's really happening when we increment i or j in the expression 2^i * 5^j, you are either multiplying by another 2 or another 5. If we restate the problem as - given a particular value of i and j, how would you find the next greater value, the solution becomes apparent.

Here are the rules we can quite intuitively enumerate:

• If there is a pair of 2s (i > 1) in the expression, we should replace them with a 5 to get the next biggest number. Thus, i -= 2 and j += 1.
• Otherwise, if there is a 5 (j > 0), we need to replace it with three 2s. So j -= 1 and i += 3.
• Otherwise, we need to just supply another 2 to increase the value by a minimum. i += 1.

Here's the program in Ruby:

i = j = 0                                                                       
20.times do                                                                     
  puts 2**i * 5**j

  if i > 1                                                                      
    j += 1                                                                      
    i -= 2                                                                      
  elsif j > 0                                                                   
    j -= 1                                                                      
    i += 3                                                                      
  else                                                                          
    i += 1                                                                      
  end                                                                                                                                                               
end

Areaway

This doesn't work as 'i' never gets larger than 4, so no multiples of 32 (2^5) will ever appear. – Acetous

Answer 20

If we are allowed to use java Collection then we can have these number in O(n^2)

public static void main(String[] args) throws Exception {
    int powerLimit = 7;  
     int first = 2;
     int second = 5;
    SortedSet<Integer> set = new TreeSet<Integer>();

    for (int i = 0; i < powerLimit; i++) {
        for (int j = 0; j < powerLimit; j++) {
            Integer x = (int) (Math.pow(first, i) * Math.pow(second, j));
            set.add(x);
        }
    }

    set=set.headSet((int)Math.pow(first, powerLimit));

    for (int p : set)
        System.out.println(p);
}

Here powerLimit has to be initialised very carefully !! Depending upon how many numbers you want.

Ovoviviparous

this produces wrong results: 2^8 = 256 is missing before 2^6*5=320. the enumeration area is triangular, not rectangular. – Attainder

@WillNess How ?? When i am setting powerLimit=9 , this snippet returns following numbers 1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 – Ovoviviparous

no, it produces 100 numbers. how do you know where to stop? you must explain this. --- I referred to 7 as present in your code snippet. for this to be a valid answer, you must explain exactly how to set the limit for a given amount of numbers, and how many numbers will it overproduce. – Attainder

Answer 21

Here is my attempt with Scala:

case class IndexValue(twosIndex: Int, fivesIndex: Int)
case class OutputValues(twos: Int, fives: Int, value: Int) {
  def test(): Boolean = {
    Math.pow(2,  twos) * Math.pow(5, fives) == value
  }
}

def run(last: IndexValue = IndexValue(0, 0), list: List[OutputValues] = List(OutputValues(0, 0, 1))): List[OutputValues] = {
  if (list.size > 20) {
    return list
  }

  val twosValue = list(last.twosIndex).value * 2
  val fivesValue = list(last.fivesIndex).value * 5

  if (twosValue == fivesValue) {
    val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex + 1)
    val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.fivesIndex).fives + 1)
    run(lastIndex, list :+ outputValues)
  } else if (twosValue < fivesValue) {
    val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex)
    val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.twosIndex).fives)
    run(lastIndex, list :+ outputValues)
  } else {
    val lastIndex = IndexValue(last.twosIndex, last.fivesIndex + 1)
    val outputValues = OutputValues(value = fivesValue, twos = list(last.fivesIndex).twos, fives = list(last.fivesIndex).fives + 1)
    run(lastIndex, list :+ outputValues)
  }
}

val initialIndex = IndexValue(0, 0)
run(initialIndex, List(OutputValues(0, 0, 1))) foreach println

Output:

OutputValues(0,0,1)
OutputValues(1,0,2)
OutputValues(2,0,4)
OutputValues(0,1,5)
OutputValues(3,0,8)
OutputValues(1,1,10)
OutputValues(4,0,16)
OutputValues(2,1,20)
OutputValues(0,2,25)
OutputValues(5,0,32)
OutputValues(3,1,40)
OutputValues(1,2,50)
OutputValues(6,0,64)
OutputValues(4,1,80)
OutputValues(2,2,100)
OutputValues(0,3,125)
OutputValues(7,0,128)
OutputValues(5,1,160)
OutputValues(3,2,200)
OutputValues(1,3,250)
OutputValues(8,0,256)

Sinkage