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 kth 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?