Last Updated: 7 Mar, 2021

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

Easy

Asked in companies

Solve now

Problem statement

Ninjas are often known for their will to never give up no matter how fierce the challenge. One such ninja was challenged by another if they could solve a problem to find the Kth number in a list of given elements (array) comprising of only 3, 5 and 7 as their prime factors. Despite the ninja’s strong will to solve the problem, you know that it could be easily solved with the help of knowledge of programming. Since the ninja does not know that you’ll have to devise an algorithm for solving the problem. Your task is to complete the given function which returns that required Kth element from the array.

For Example:

Input: 'K' = 10
Output: 45

The array will contain elements that only have 3, 5 or 7 as their prime factors i.e. of  the following form:-  3,5,7,9,15,21,25,…. Therefore we can see from the above pattern of elements that 45 would be the 10th element in the array which is our  required answer.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. 
Then the test cases follow:-

The first and the only line of each test contains an integer 'K', denoting the Kth number that we want.

Output format:

For each test case, return the Kth element from the array.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= K <= 3 * 10^3

Time limit: 1 second

Solve now

Approaches

01 Approach

The key observation here is to notice a simple fact that the Kth element would always be of the form:-

Kth Multiple of 3, 5 and 7 = 3k * 5k * 7k

We can simply iterate through from 1 to ‘k-1’ and Initialize three queues say Q3, Q5, Q7 and an integer variable say ‘X’ = 1. Keep track of the minimum element among the queues and make that the next value of ‘X’ in our array.

The algorithm for the same can be as follows:-

Initialize three queues say Q3, Q5, Q7 and an integer variable say 'NEXT_ELEMENT' = 1 which would keep track of our next element which we would obtain in our array.
Iterate i from 1 to K-
1. Insert 'NEXT_ELEMENT' * 3, 'NEXT_ELEMENT' * 5, 'NEXT_ELEMENT' * 7 into Q1,Q2,Q3 respectively.
2. Now find the minimum element among the front of the queues (Q1.front, Q2.front, Q3.front)
  1. if nextElement equals Q3.front then do Q3.pop
  2. if nextElement equals Q5.front then do Q5.pop
  3. if nextElement equals Q7.front then do Q7.pop
We finally return 'NEXT_ELEMENT'.

Solve now