Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
I think the interview want to ask you to do it in constant memory. Using O(n) memory makes this quite trivial. Or at least using O(logn) memory because the encoding size for input n would be logn. An O(n) for memory solution is an exponential memory solution. –  InstructedA Jul 18 at 11:05

5 Answers 5

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.

share|improve this answer
1  
Hi, you can see why I was confused during the interview I hope. In fact, the example provided is outputs from the set described in the question. 1 = 2^0*5^0, 2 = 2^1*5^0, 4 = 2^2*5^0, 5 = 2^0*5^1, 8 = 2^3*5^0, 10 = 2^1*5^1. –  Justin Skiles Jul 17 at 17:56
    
Are those repeated .Remove() and .Add() going to trigger bad behavior from the garbage collector, or will it figure things out? –  Snowbody Jul 18 at 14:25
1  
@Snowbody: The op's question is an algorithms question, so it's somewhat irrelevant. Ignoring that, your first concern should be dealing with very large integers, as this becomes a problem far sooner than garbage collector overhead. –  Brian Jul 18 at 14:41

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 3a5b7c 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.

share|improve this answer

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.

share|improve this answer
    
Great answer. I have similar idea that I haven't coded. In this idea, I keep a tracker for 2 and 5. This will track the maximum n and m that have been used through out the numbers in the sequence so far. At each iteration, n or m might or might not go up. We create a new number as 2^(max_n+1)*5^(max_m+1) then reduce this number in exhaustive recursive manner each call reducing the exponent by 1 until we get the minimum that is bigger than the current number. We update max_n, max_m as needed. This's constant mem. Can be O(log^2(n)) mem if DP cache is used in reduction call –  InstructedA Jul 19 at 14:53
    
Interesting. The optimization here is that it doesn't need to consider all pairs of m & n, because we know the correct m, n will produce the closest multiplier to 1. So I only need to evaluate m = -i to max_i, and I can just calculate n, throwing in some garbage for roundoff (I was sloppy and just iterated -1 to 1, but it bears more thinking ;)). –  Rob Y Jul 19 at 14:59
    
However, I'm kind of thinking like you... the sequence is going to be deterministic... it's really like a big Pascal's triangle i + 1 in one direction and j + 1 in the other. So the sequence should be mathematically deterministic. For any node in the triangle, there's always going to be a mathematically determined next node. –  Rob Y Jul 19 at 15:01
1  
There might be a formula for the next one, we might not need to do search. I don't know for sure. –  InstructedA Jul 19 at 15:05
    
When I think about it, the algebraic form of the next one might not exist (not all deterministic problems have algebraic form for solutions) in addition when there are more primes than just 2 and 5, the formula might be quite hard to find if one really wants to work out this formula. If some one knows the formula, I probably would read about it a bit, this sounds interesting. –  InstructedA Jul 19 at 15:32

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.

share|improve this answer
1  
Please don't create 2 answers for one question. Edit your first answer and fix the problems you found with it. –  GlenH7 Jul 18 at 0:43
1  
What algorithm does this use? Why does it work? The key part to the question being asked is Does anyone have advice on how to solve such a problem? in an attempt to gain understanding of the underlying problem. A code dump does not answer that question well. –  MichaelT Jul 18 at 1:39
    
Good point, I explained my thinking. –  Snowbody Jul 18 at 4:00
    
+1 While this is roughly equivalent to my second snippet, your use of immutable edges makes it clearer how the edge count grows. –  Brian Jul 18 at 13:08
    
This is definitely slower than Brian's revised snippet, but its memory usage behavior should be a lot better as it isn't constantly deleting and adding elements. (Unless the CLR or SortedSet<> has some method of reusing elements that I don't know about) –  Snowbody Jul 18 at 14:24

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.

share|improve this answer
    
great answer, I think there is also a pattern in increasing the sequence for any number primes –  InstructedA Jul 21 at 1:16
    
@randomA Thanks. After some further thought, I reached the conclusion that as it currently stands my algorithm is not as fast as I thought it was. If there's a faster way of evaluating "Attempt to increase i/j", I think that's the key to getting logarithmic time. –  VF1 Jul 21 at 1:59
    
I was thinking in that: we know that to increase the number, we have to increase the number of one of the primes. For example, one way to increase is to mul with 8 and divide by 5. So we get the set of all ways to increase and decrease the number. This will only contain basic ways like mul 8 div 5 and not mul 16 div 5. There is also another set of basic ways to decrease. Sort these two sets by their increase or decrease factor. Given a number, the next one can be found by finding an applicable increase way with smallest factor from the increase set.. –  InstructedA Jul 24 at 11:50
    
.. applicable means there are enough primes to perform mul and div. Then we find a decrease way to the new number, so starting with the one that decreases the most. Keep using new ways to decrease and we stop when the new number is smaller than the original given number. Since the set of primes is constant, this means constant size for two sets. This needs a little bit of proof as well, but it looks like constant time, constant memory at each number to me. So constant memory and linear time for printing n numbers. –  InstructedA Jul 24 at 12:04
    
@randomA where did you get division from? Do you mind making a full answer - I don't quite understand your comments. –  VF1 Jul 25 at 1:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.