Find the kth number with prime factors 3, 5 and 7

Find the kth number with prime factors 3, 5 and 7

Design an algorithm such that we have to find the k th element in the array such that their only prime factors are 3,5 an 7.
Example: Array will contain 1,3,5,7,9,15,21,25,...
We have to return the kth element in array



Algo

Step 1: Initialize three queues say q3,q5,q7 and an integer variable say x =1.

Step 3: for i=1  to k-1

a) Insert x*3,x*5,x*7 into q1,q2,q3 respectively

b) x=minimum (q1.front, q2.front, q3.front)

c) if x==q1.front then do q1.pop

d) if x==q2.front then do q2.pop

e) if x==q3.front then do q3.pop

Step 4:  Print x

Code in C++ :

#include <queue>

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{

    int k=10;

    int a=3,b=5,c=7,x=1;

    queue<int>q3,q5,q7;

    for(int i=1;i<k;i++)

    {

        q3.push(x*3);

        q5.push(x*5);

        q7.push(x*7);

        x=min(q3.front(),min(q5.front(),q7.front()));

        if(x==q3.front())

        {

            q3.pop();

        }

        if(x==q5.front())

        {

            q5.pop();

        }

        if(x==q7.front())

        {

            q7.pop();

        }

    }

    cout<<x<<endl;

    return 0;

}

Complexity:

O(k) time complexity

Thanks Dheeraj for providing Question and Solution.