Find the Kth least number for expression (2^x)*(3^y)*(5^z)

In the expression

2^x * 3^y * 5^z

The x, y and z can take non negativ开发者_Python百科e integer value (>=0).

So the function would generate a series of number 1,2,3,4,5,6,8,9,10,12,15,16....

• I have a brute force solution.
• I would basically iterate in a loop starting with 1 and in each iteration I would find if the current number factors are only from the set of 2,3 or 5.

What I would like to have is an elegant algorithm.

This is an interview question.

---

This can be solved using a priority queue, where you store triplets (x, y, z) sorted by the key 2^x3^y5^z.

1. Start with only the triplet (0, 0, 0) in the queue.

2. Remove the triplet (x, y, z) with the smallest key from the queue.

3. Insert the three triplets (x+1, y, z), (x, y+1, z) and (x, y, z+1) in the queue. Make sure you don't insert anything that was already there.

4. Repeat from step 2 until you've removed k triplets. The last one removed is your answer.

In effect, this becomes a sorted traversal of this directed acyclic graph. (First three levels shown here, the actual graph is of course infinite).

---

This page lists solutions in bazillion programming languages. As usual, the Haskell version is particularly compact and straightforward:

hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
     where merge (x:xs) (y:ys)
            | x < y = x : xs `merge` (y:ys)
            | x > y = y : (x:xs) `merge` ys
            | otherwise = x : xs `merge` ys

Update As Will Ness has noted, there is a ready-made function in Data.List.Ordered which is a better choice than my merge (and it has a better name, too).

import Data.List.Ordered (union)
hamming = 1 : map (2*) hamming `union` map (3*) hamming `union` map (5*) hamming

---

The most straightforward solution I can think of:

    int[] factors = {2, 3, 5};
    int[] elements = new int[k];
    elements[0] = 1;
    int[] nextIndex = new int[factors.length];
    int[] nextFrom = new int[factors.length];
    for (int j = 0; j < factors.length; j++) {
        nextFrom[j] = factors[j];
    }
    for (int i = 1; i < k; i++) {
        int nextNumber = Integer.MAX_VALUE;
        for (int j = 0; j < factors.length; j++) {
            if (nextFrom[j] < nextNumber) {
                nextNumber = nextFrom[j];
            }
        }
        elements[i] = nextNumber;
        for (int j = 0; j < factors.length; j++) {
            if (nextFrom[j] == nextNumber) {
                nextIndex[j]++;
                nextFrom[j] = elements[nextIndex[j]] * factors[j];
            }
        }
    }
    System.out.println(Arrays.toString(elements));

This generates the first k elements of that set in ascending order in O(k) space and time.

Note that it is necessary to consume nextNumber from all j that provide it in order to eliminate duplicates (2*3 = 3*2 after all).

Edit: The algorithm uses the same approach as the haskell one posted by n.m.

---

This might be testing more than your knowledge of algorithms, to include how you think, solve problems, and work in a team.

It is important to have a decent specification of the problem before you begin. Some of the unknowns, as described, include:

• are there bounds on K?
• do you want a known algorithm or is ad-hoc brute force ok?
• memory usage vs compute time? (maybe one or the other matters)
• how fast does it have to calculate vs how much time do I have to develop it?
• should results be cached?

Asking the interviewer about some or all of these questions may be at least as important as being able to answer the question asked. Of course, you can paint yourself into a corner this way, which can even be part of the test....

---

Since the problem can be converted to finding Kth least number of

 f(x,y,z) = x log(2) + y log(3) + z log(5),

the algorithm might be following

1. starts with f(x,y,z) = f(0,0,0)

2. given current least number f(i,j,k) = v, you gotta find (x,y,z) such that f(x,y,z) is the closest to v and > v. Since

   log(2)<log(3)<2log(2)<log(5)

   We can say

   0<=i-2<=x<=i+2, 0<=j-1<=y<=j+1 & 0<=k-1<=z<=k+1 such that f(x,y,z) > v

So since this is to find the minimum of 45 values in each step and I would say it's O(K) algorithm. Of course, the number 45 can be reduced by imposing more conditions such as (x,y,z)!=(i,j,k).

---

These are the Hamming numbers, which I used as an example in SRFI-41. This was the code I used there:

(define hamming
  (stream-cons 1
    (stream-unique =
      (stream-merge <
        (stream-map (lsec * 2) hamming)
        (stream-map (lsec * 3) hamming)
        (stream-map (lsec * 5) hamming)))))

---

There is a very elegant solution to this kind of problem. Algorithm and coding is simple. Time complexity is O(n)

I saw a similar problem somewhere. The problem was to generate the numbers of the form 2^x.3^y in ascending order.

So here goes.

int kthsmallest(int k){

    int two = 0, three = 0, five = 0;
    int A[k];
    A[0] = 1;
    for (int i=1; i<k; i++){
        int min = (A[two] * 2 <= A[three] * 3)? A[two] * 2: A[three] * 3;
        min = (min <= A[five] * 5)? min: A[five] * 5;
        A[i] = min;
        if (min == A[two] * 2)
            two++;
        if (min == A[three] * 3)
            three++;
        if (min == A[five] * 5)
            five++;
    }
    return A[k-1];
}

The algorithm is basically - keep three pointers for x, y, z. In the code, I used two, three and five. In every iteration, check which one smaller (2^x, 3^y or 5^z). Put that number in the ith index and increment the corresponding value of x or y or z. If there are more than one min values, then increment both the pointers.

---

Below is a working java based solution to find kth smallest number which has factors as only 2,3 and 5. Here 2*3*5 is considered as the smallest factor.

import java.util.Comparator;
import java.util.PriorityQueue;
public class KthSmallestFactor {

    public static void main(String[] args){

        for(int i=1;i<=10;i++){
            System.out.println(kthSmallest(i));
        }
    }

    private static int kthSmallest(int k){
        PriorityQueue<Triplet> p = new PriorityQueue<Triplet>(10, new Comparator<Triplet>() {
            public int compare(Triplet t1, Triplet t2) {
                int score1 = (int) (Math.pow(2, t1.a) * Math.pow(3, t1.b) * Math.pow(5, t1.c)) ; 
                int score2 = (int) (Math.pow(2, t2.a) * Math.pow(3, t2.b) * Math.pow(5, t2.c));
                return score1 -score2;
            }
        });

        p.add(new Triplet(1, 1, 1));
        int count =1;
        while(count <k){
            Triplet top = p.poll();
            count++;
            int a = top.a;
            int b = top.b;
            int c = top.c;
            Triplet t = new Triplet(a+1, b, c);
            if(!p.contains(t)){
                p.add(t);
            }
            t = new Triplet(a, b+1, c);
            if(!p.contains(t)){
                p.add(t);
            }
            t = new Triplet(a, b, c+1);
            if(!p.contains(t)){
                p.add(t);
            }
        }
        Triplet kth = p.poll();
        System.out.println("a: "+kth.a+"b: "+kth.b+"c: "+kth.c);
        return (int) (Math.pow(2, kth.a) * Math.pow(3, kth.b) * Math.pow(5, kth.c));
    }
}
class Triplet{
    int a ;
    int b;
    int c;

    public Triplet(int a , int b, int c){
        this.a = a;
        this.b=b;
        this.c = c;
    }

    public boolean equals(Object other){
        Triplet t = (Triplet)other;
        return this.a== t.a && this.b==t.b && this.c == t.c; 
    }
}

---

Start with x = y = z = 0; At each iteration compute three n's:

nx = 2^(x+1)*3^y*5^z
ny = 2^x*3^(y+1)*5^z
nz = 2^x*3^y*5^(z+1)

Find the least n among the three:

n = min(nx, ny, nz).

Increase either x, y, or z:

If n == nx -> x = x + 1
If n == ny -> y = y + 1
If n == nz -> z = z + 1

Stop after the K-th iteration and return n.