Sunday, July 7, 2013

Find Nth number in x2x3x5 sequence

Problem:
Following sequence is given:
1,2,3,4,5,6,8,9,10,12,15,16,18,20,24
In this sequence, each number is multiple of 2,3 or 5 only.
This sequence does not contain 7 & 14 as these number has sequence 7 as multiple.
So, if you are given N find the Nth number of this sequence.

Solution:
A dynamic programming solution (assume the sequence starts with 2):
  1. Maintain a counter, that is initialized to 1 and start from an initial value v, say 2. 
  2. Keep incrementing the value v and check if it is divisible by 2 or 3 or 5. 
  3. If divisible, check if the corresponding quotient of v/2 or v/3 or v/5 is present in the solutions to subproblems, that are already computed. If yes increment the counter. 
  4. Return value v when the counter becomes N.
void findN(int N) {
    HashMap<Integer, Integer> DPMap = new HashMap<Integer, Integer>();
    int temp = 2, i = 1;
    DPMap.put(1, 1);
    DPMap.put(2, 2);

    while (i < N) {
        temp++;
        if ((temp % 2 == 0 && DPMap.containsKey(temp / 2))
                || (temp % 3 == 0 && DPMap.containsKey(temp / 3))
                || (temp % 5 == 0 && DPMap.containsKey(temp / 5)))
        {
            i++;
            DPMap.put(temp, temp);
        }
    }
    System.out.println("The required number = " + temp);
}


Complexity:
time - O(n)
space - O(n)
Links and credits:
http://www.careercup.com/question?id=20810664

No comments:

Post a Comment