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 2: 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 3: Print x
Code in C++ :
#include <queue>
#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.