**Problem:**find the

*k*th positive integer that only have factors as 3, 5, or 7. For example, the first integer is 3, then 5, 7, 9, 15, 21......

**Solution:**It is a DP problem where we should leverage on previous status. Then we can avoid redundant computation. The main ideas are stated as follow:

- Have three queues, let us say Q3, Q5 and Q7. Put 3, 5 and 7 in these queues, receptively.
- Then select the smallest element among the three queues by just comparing the heads of the queues. If the smallest element
*s*is from Q3, Q3.enque(*s**3), Q5.enque(*s**5) and Q7.enque(*s**7); If the smallest element*s*is from Q5, Q5.enque(*s**5) and Q7.enque(*s**7); If the smallest element*s*is from Q7, Q7.enque(*s**7). Since we strictly follow the ascending order, we guarantee that there is not redundant computation. - Repeat the selection (step 2) for
*k*times, what we get is the*k*th positive integer that only have factors as 3, 5, or 7. - The time complexity and space complexity are both O(k).

hi tristan,

ReplyDeleteyou can have it in O(1) space complexity -- just keep counters n3, n5 and n7:

n3 = 0, n5 = 0, n7 = 0

x = 1

for i in [0, k - 1]:

..x3 = x * 3

..x5 = x * 5

..x7 = x * 7

..if x3 < x5 and x3 < x7:

....n3 += 1

....x = x3

..else if x5 < x3 and x5 < x7:

....n5 += 1

....x = x5

..else:

....n7 += 1

....x = x7

Hi route40, thanks for the comment. But it seems that the code you provided has some problem. Please see my comment in line.

Deletefor i in [0, k - 1]:

..x3 = x * 3

..x5 = x * 5

..x7 = x * 7

<------------- when we reach here, "x3<x5 and x3<x7" will always hold. Therefore we always enter the first if branch (I mean "if x3 < x5 and x3 < x7"). Let me know if I am wrong.

..if x3 < x5 and x3 < x7:

....n3 += 1

....x = x3

..else if x5 < x3 and x5 < x7:

....n5 += 1

....x = x5

..else:

....n7 += 1

....x = x7

How is the complexity O(k)? I'm assuming that the queue is a priority queue.

ReplyDeleteAlso, if using a normal queue, how do you guarantee that each queue is ordered in increasing order?