Print the next smallest from 2^i * 5^j where i,j >= 0

Question

I was asked this question during a technical phone screening recently and didn't do well. The question is included verbatim below.

Generate {2^i * 5^j | i,j >= 0} sorted collection. Continuously print the next smallest value.

Example: { 1, 2, 4, 5, 8, 10...}

"Next smallest" makes me think a min-heap is involved, but I didn't really know where to go from there and no assistance was provided by the interviewer.

Does anyone have advice on how to solve such a problem?

Answer 1

Let's reword the problem: Output every number from 1 to infinity such that the number has no factors except 2 and 5.

Below is a simple C# snippet:

for (int i = 1;;++i)
{
    int num = i;
    while(num%2 == 0) num/=2;
    while(num%5 == 0) num/=5;
    if(num == 1) Console.WriteLine(i);
}

Kilian's/QuestionC's approach is much more performant. C# snippet with this approach:

var itms = new SortedSet<int>();
itms.Add(1);
while(true)
{
    int cur = itms.Min;
    itms.Remove(itms.Min);
    itms.Add(cur*2);
    itms.Add(cur*5);
    Console.WriteLine(cur);
}

SortedSet prevents duplicate insertions.

Basically, it works by ensuring that the next number in the sequence is in itms.

Proof that this approach is valid:
The algorithm described ensures that after for any number output in the form 2^i*5^j, the set now contains 2^(i+1)*5^j and 2^i*5^(j+1). Suppose the next number in the sequence is 2^p*5^q. There must exist a previously output number of the form 2^(p-1)*5^(q) or 2^p*5^(q-1) (or both, if neither p nor q are equal to 0). If not, then 2^p*5^q is not the next number, since 2^(p-1)*5^(q) and 2^p*5^(q-1) are both smaller.

The second snippet uses O(n) memory (where n is the number of numbers that have been output), since O(i+j) = O(n) (because i and j are both less than n), and will find n numbers in O(n log n) time. The first snippet finds numbers in exponential time.

Answer 2

This is a common enough interview question that it's useful to know the answer. Here's the relevant entry in my personal crib sheet:

• to generate the numbers of the form 3^a5^b7^c in order, start with 1, stuff all three possible successors (3, 5, 7) into an auxiliary structure, then add the smallest number from it to your list.

In other words, you need a two-step approach with an additional sorted buffer to solve this efficiently. (A good longer description is in Cracking the Coding Interview by Gayle McDowell.

Answer 3

Here's an answer that runs with constant memory, at the expense of CPU. This is not a good answer in the context of the original question (i.e. answer during an interview). But if the interview is 24 hours long, then it's not so bad. ;)

The idea is that if I have n which is a valid answer, then the next in the sequence is going to be n times some power of two, divided by some power of 5. Or else n times a power of 5, divided by a power of two. Provided it divides evenly. (...or the divisor can be 1 ;) in which case you're just multiplying by 2 or 5)

For example, to go from 625 to 640, multiply by 5 ** 4 / 2 ** 7. Or, more generally, multiply by some value of 2 ** m * 5 ** n for some m, n where one is positive and one is negative or zero, and the multiplier divides the number evenly.

Now, the tricky part is find the multiplier. But we know a) the divisor must divide the number evenly, b) the multiplier must be greater than one (the numbers keep increasing), and c) if we pick the lowest multiplier greater than 1 (i.e. 1 < f < all other f's), then that's guaranteed to be our next step. The step after that will be it's lowest step.

The nasty part is finding the value of m, n. There are only log(n) possibilities, because there are only so many 2's or 5's to give up, but I had to add a factor of -1 to +1 as a sloppy way to deal with roundoff. So we only have to iterate through O(log(n)) each step. So it's O(n log(n)) overall.

The good news is, because it takes a value and finds the next value, you can start anywhere in the sequence. So if you want the next one after 1 billion, it can just find it by iterating through the 2 / 5's or 5 / 2's and picking the smallest multiplier greater than 1.

(python)

MAX = 30
F = - math.log(2) / math.log(5)

def val(i, j):
    return 2 ** i * 5 ** j

def best(i, j):
    f = 100
    m = 0
    n = 0
    max_i = (int)(math.log(val(i, j)) / math.log(2) + 1) if i + j else 1
    #print((val(i, j), max_i, x))
    for mm in range(-i, max_i + 1):
        for rr in {-1, 0, 1}:
            nn = (int)(mm * F + rr)
            if nn < -j: continue
            ff = val(mm, nn)
            #print('  ' + str((ff, mm, nn, rr)))
            if ff > 1 and ff < f:
                f = ff
                m = mm
                n = nn
    return m, n

def detSeq():

    i = 0
    j = 0
    got = [val(i, j)]

    while len(got) < MAX:
        m, n = best(i, j)

        i += m
        j += n
        got.append(val(i, j))

        #print('* ' + str((val(i, j), m, n)))
        #print('- ' + str((v, i, j)))

    return got

I validated the first 10,000 numbers this generates against the first 10,000 generated by the sorted list solution, and it works at least that far.

BTW the next one after a trillion seems to be 1,024,000,000,000.

...

Hm. I can get O(n) performance -- O(1) per value (!) -- and O(log n) memory usage by treating best() as a lookup table that I extend incrementally. Right now it saves memory by iterating each time, but it's doing a lot of redundant calculations. By holding those intermediate values -- and a list of min values -- I can avoid the duplicate work & speed it up a lot. However, the list of intermediate values will grow with n, hence the O(log n) memory.

Answer 4

Brian was absolutely right -- my other answer was way too complicated. Here's a simpler and faster way to do it.

Imagine Quadrant I of the Euclidean plane, restricted to the integers. Call one axis the i-axis and the other axis the j-axis.

Obviously, points near to the origin will be picked before points far from the origin. Also note that the active area will move away from the i-axis before it moves away from the j-axis.

Once a point has been used, it won't ever be used again. And a point can only be used if the point directly below it or to the left of it has already been used.

Putting these together, you can imagine a "frontier" or "leading edge" that starts around the origin and them spreads up and right, spreading along the i-axis farther than on the j-axis.

In fact, we can figure out something more: there will be at most one point on the frontier/edge for any given i-value. (You have to increment i more than 2 times to equal an increment of j.) So, we can represent the frontier as a list containing one element for each i coordinate, only varying with the j coordinate and the function value.

Each pass, we pick the minimum element on the leading edge, and then move it in the j-direction once. If we happen to be raising the last element, we add on a new last more element with an incremented i-value and a j-value of 0.

using System;
using System.Collections.Generic;
using System.Text;

namespace TwosFives
{
    class LatticePoint : IComparable<LatticePoint>
    {
      public int i;
      public int j;
      public double value;
      public LatticePoint(int ii, int jj, double vvalue)
      {
          i = ii;
          j = jj;
          value = vvalue;
      }
      public int CompareTo(LatticePoint rhs)
      {
          return value.CompareTo(rhs.value);
      }
    }


    class Program
    {
        static void Main(string[] args)
        {
            LatticePoint startPoint = new LatticePoint(0, 0, 1);

            var leadingEdge = new List<LatticePoint> { startPoint } ;

            while (true)
            {
                LatticePoint min = leadingEdge.Min();
                Console.WriteLine(min.value);
                if (min.j + 1 == leadingEdge.Count)
                {
                    leadingEdge.Add(new LatticePoint(0, min.j + 1, min.value * 2));
                }
                min.i++;
                min.value *= 5;
            }
        }
    }
}

Space: O(n) in number of elements printed so far.

Speed: O(1) inserts, but those aren't done every time. (Occasionally longer when the List<> has to grow, but still O(1) amortized). The big time sink is the search for the minimum, O(n) in the number of elements printed so far.

Answer 5

The set-based solution was probably what your interviewer was looking for, however, it has the unfortunate consequence of having O(n) memory and O(n lg n) total time for sequencing n elements.

A bit of math helps us find a O(1) space and O(n sqrt(n)) time solution. Notice that 2^i * 5^j = 2^(i + j lg 5). Finding the first n elements of {i,j > 0 | 2^(i + j lg 5)} reduces to finding the first n elements of {i,j > 0 | i + j lg 5} because the function (x -> 2^x) is strictly monotonically increasing, so the only way for some a,b that 2^a < 2^b is if a < b.

Now, we just need an algorithm to find the sequence of i + j lg 5, where i,j are natural numbers. In other words, given our current value of i, j, what minimizes the next move (i.e., gives us the next number in the sequence), is some increase in one of the values (say j += 1) along with a decrease in the other (i -= 2). The only thing that's limiting us is that i,j > 0.

There are only two cases to consider - i increases or j increases. One of them must increase since our sequence is increasing, and both don't increase because otherwise we're skipping the term in which we only have one of i,j increase. Thus one increases, and the other stays the same or decreases. Expressed in C++11, the whole algorithm and its comparison to the set solution are available here.

This achieves constant memory since there are only a constant amount of objects allocated in the method, aside from the output array (see link). The method achieves logarithmic time every iteration since for any given (i,j), it traverses for the best pair (a, b) such that (i + a, j + b) is the smallest increase in the value of i + j lg 5. This traversal is O(i + j):

Attempt to increase i:
++i
current difference in value CD = 1
while (j > 0)
  --j
  mark difference in value for
     current (i,j) as CD -= lg 5
  while (CD < 0) // Have to increase the sequence
    ++i          // This while will end in three loops at most.
    CD += 1
find minimum among each marked difference ((i,j) -> CD)

Attempt to increase j:
++j
current difference in value CD = lg 5
while (j > 0)
  --i
  mark difference in value for
     current (i,j) as CD -= 1
  while (CD < 0) // have to increase the sequence
    ++j          // This while will end in one loop at most.
    CD += lg 5
find minimum among each marked difference ((i,j) -> CD)

Every iteration attempts to update i, then j, and goes with the smaller update of the two.

Since i and j are at most O(sqrt(n)), we have total O(n sqrt(n)) time. i and j grow at the rate of the square of n since for any maximum valiues imax and jmax there exist O(i j) unique pairs from which to make our sequence if our sequence is n terms, and i and j grow within some constant factor of one another (because the exponent is comprised of a linear combination fo the two), we know that i and j are O(sqrt(n)).

There's not too much to worry about regarding floating point error - since the terms grow exponentially, we'd have to deal with overflow before flop error catches up with us, by several magnitudes. I'll add more discussion to this if I have time.