Mathematics15

Q15. Design an algorithm to find the nth number such that the only prime factors are 3, 5, and 7.
Answer:

import java.util.LinkedList;
import java.util.Queue;

public class Mathematics15 {
    public static int magicNumber(int n) {
        Queue<Integer> q3 = new LinkedList<Integer>();
        Queue<Integer> q5 = new LinkedList<Integer>();
        Queue<Integer> q7 = new LinkedList<Integer>();

        if (n <= 0) {
            return 0;
        }

        // 1st magic number is 1 = 3^0*5^0*7^0
        int val = 1;
        q3.add(3);
        q5.add(5);
        q7.add(7);

        // we’ve done one iteration already for 1st
        // magic number
        for (int i = 2; i <= n; i++) {
            val = min(q3.peek(), q5.peek(), q7.peek());
            if (val == q3.peek()) {
                q3.poll();
                q3.add(val * 3);
                q5.add(val * 5);
                q7.add(val * 7);
            } else if (val == q5.peek()) {
                q5.poll();
                q5.add(val * 5);
                q7.add(val * 7);
            } else {
                // now it must must be from q7
                q7.poll();
                q7.add(val * 7);
            }
        }
        return val;
    }

    // function to find min of 3 integers
    public static int min(int a, int b, int c) {
        int min = a;
        if (b < a)
            min = b;
        if (c < min)
            min = c;
        return min;
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 20; i++) {
            System.out.println("Magic Number" + i + "= " + magicNumber(i));
        }
    }
}