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

Easy
0/40
Average time to solve is 10m
profile
Contributed by
6 upvotes
Asked in companies
AdobeSamsung

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
9         
5         
10
Sample Output 1:
35
15
45
Explanation for sample 1:
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,27,35,45….
Therefore we can see from the above pattern of elements that the 9th, 5th and 10th elements would be 35, 15 and 45 respectively.
Sample Input 2:
2
12
8
Sample Output 2:
63
27
Hint

Can we find the minimum value which would be next in the sequence to solve this problem?

Approaches (1)
Kth number with only prime factors of 3, 5 and 7

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'.
Time Complexity

O(K), where ‘K’ is the number that is required from the array.

 

Now, since there are K iterations in total. So the time complexity grows by O(K).

Space Complexity

O(1),

 

Constant space is used.

Code Solution
(100% EXP penalty)
Find the kth number with prime factors 3, 5 and 7
Full screen
Console