## 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.