CareerCup

Seems the sequence mentioned in the question should start from 2 as 1 is not a multiple of 2 or 3 or 5.

An O(n) solution using DP can solve the problem by computing the values from 1st to the Nth number.

0. Maintain a counter, that is initialized to 1 and start from an initial value v, say 2.
1. Keep incrementing the value v and check if it is divisible by 2 or 3 or 5.
2. 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.
3. Return value v when the counter becomes N.

import java.util.HashMap;
import java.util.Scanner;

public class Multiplesof2and3and5 {

	public static void main(String[] args) {
		System.out.println("Please input N:");
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		findN(N);
	}

	private static 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);
	}
}

def num(n):
    return int(n >= 1) + n / 2 + n / 3 + n / 5 - n / 6 - n / 15 - n / 10 + n / 30

def nth(n):
    l = n
    r = 2 * n
    while num(r) < n:
        r = 2 * r
    while l < r:
        m = (l + r) / 2
        c = num(m)
        if c == n: return m
        if c > n: r = m
        else: l = m + 1
    return l

print nth(100000000000000)

It is basically dp problem.I thought of following recursion but I cant optimize it further
a[i]=min{a[i-5]*2,3,5;a[i-4]*2,3,5;a[i-3]*2,3,5;a[i-2]*2,3,5;a[i-1]*2,3,5} and that num>a[i]

-take array of three elements values{2,3,5}
-take array of three in indices indices{0,0,0}
-create array result[N] to store result;
- take min(values), add to result, check with values and if it is equal to first value in values
then increment first index of indices array and multiply with 2 the result[indices[0]] and store in values[0], same way for 3 and 5, do till Nth number

This is the standard problem of Ugly numbers. A good DP solution is given at geeksforgeeks.org/ugly-numbers/

@recursive based logic

/*
 * 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.
 * */

public class FindNthNumber {
	/**
	 * @param MultiplList
	 *            --all has to prime nmbers
	 * @param Nth
	 *            number
	 */
	int curr_size = 0;

	public int FindNthNumberfromSequence(int[] MultiplList, int n) {
		curr_size = 0;
		int[] list = new int[n];
		for (int j = 0; j < n; j++)
			list[j] = Integer.MAX_VALUE;
		getListforPower(MultiplList, n, 1, list, n);
		//for (int i = 0; i < n; i++)
			//System.out.println(list[i]);
		return list[n - 1];
	}

	private void getListforPower(int[] multiplList, int k, int value,
			int[] list, int n) {
		if (curr_size >= n && value >= list[n - 1])
			return;
		int size = (n > curr_size) ? ++curr_size : n;
		int v = value;
		// System.out.println(v+"<-->"+list[n-1]+ " ,"+size);
		for (int j = 0; j < size; j++) {
			if (value == list[j])
				break;
			if (value < list[j]) {
				int temp = list[j];
				list[j] = v;
				v = temp;
			}
		}
		if (k == 0)
			return;
		for (int j = 0; j < multiplList.length; j++)
			getListforPower(multiplList, k - 1, value * multiplList[j], list, n);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		FindNthNumber test = new FindNthNumber();
		int listofmultipliers[] = { 2, 3, 8 };
		int output = test.FindNthNumberfromSequence(listofmultipliers, 11);
		System.out.print(output);

	}

}

output: 24

import java.util.*;
public class Nthterm{
	public static void main(String args[]){
	int ar[]=new int[50];
	ar[0]=1;
	PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
	for(int i=1;i<50;i++){
			queue.add(ar[i-1]*2);
			queue.add(ar[i-1]*3);
			queue.add(ar[i-1]*5);
			int j=0;
			while(j<=ar[i-1] || j%7==0 )	j = queue.poll();
			ar[i]=Integer.valueOf(j);
	}
		System.out.println(Arrays.toString(ar));
	}

}

public static void main(String args[]) {
 		int N =10; // Input N value
		int noCnt = 1;
		System.out.print(1 + ",");
		for(int i=2,twoC = 2, threeC = 2, fiveC = 2,sevenC=2;noCnt<N;i++,twoC++,threeC++,fiveC++,sevenC++)
		{
			
			if(twoC  == 2){
				twoC = 0;
			}
			if(threeC  == 3){
				threeC = 0;
			}
			if(fiveC  == 5){
				fiveC = 0;
			}
			if(sevenC == 7){
				sevenC = 0;
				continue;
			}
			if(twoC == 0 || threeC == 0 || fiveC == 0){
				System.out.print(i + ",");
				noCnt++;
			}
		}
	}

}

…
int result=1;
int a=20; //20 is the index number to find
for(int i=1;i<a;i++)
{
if( ((result+1)%2==0) || ((result+1)%3==0) || ((result+1)%5==0) )
		result=result+1;
else
	        result=result+2;

}

..
..
for(i=2;;i++)
{
if((i%2==0 || i%3==0 || i%5==0))
{
count++;
if(count == n)
return i;
}
}

...

assume here i start from 2 ..
n is the nth term ..
and count is variable set to 0 and incremented as we'll find a number we need.. if count and n are same then return i ...

1. Initialize list 'result' and queues Q2, Q3 and Q5
2. Insert 1 into result.
3. Insert 1*2, 1*3 and 1*5 into Q2, Q3 and Q5 respectively.
4. Let x be the minimum element in Q2, Q3 and Q5. Append x to result.
5. If x was found in:

Q2 -> append x*2, x*3 and x*5 to Q2, Q3 and Q5. Remove x from Q2.
Q3 -> append x*3 and x*5 to Q3 and Q5. Remove x from Q3.
Q5 -> only append x*5 to Q5. Remove x from Q5.
We do not need to append x*2 and x*3 to all lists because
they will already be found in another list.
6. Repeat steps 4 - 6 until we’ve found k elements.

public static void main(String[] args) {

	List<Integer> numbers = new ArrayList<Integer>();
	numbers.add(1);
	LinkedList<Integer> q2 = new LinkedList<Integer>();
	LinkedList<Integer> q3 = new LinkedList<Integer>();
	LinkedList<Integer> q5 = new LinkedList<Integer>();
	List<LinkedList<Integer>> queues = new ArrayList<LinkedList<Integer>>(3);
	q2.add(2);
	q3.add(3);
	q5.add(5);
	queues.add(q2);
	queues.add(q3);
	queues.add(q5);

	int k = 15;
	for (int i = 1; i < k; i++) {
	    int min = Integer.MAX_VALUE;
	    int minQueue = 0;
	    for (int j = 0; j < 3; j++) {
		if (queues.get(j).getFirst() < min) {
		    min = queues.get(j).getFirst();
		    minQueue = j;
		}
	    }
	    queues.get(minQueue).removeFirst();
	    numbers.add(min);
	    switch (minQueue) {
	    case 0:
		q2.add(min * 2);
	    case 1:
		q3.add(min * 3);
	    case 2:
		q5.add(min * 5);

	    }
	}

	System.out.println(numbers);
    }