Sunday, July 17, 2011

Find the Kth Positive Integer That Can Be Divided Only by 3, 5 or 7

Problem: find the kth 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:

  1.  Have three queues, let us say Q3, Q5 and Q7. Put 3, 5 and 7 in these queues, receptively.
  2. 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.
  3. 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.
  4. The time complexity and space complexity are both O(k).

3 comments:

  1. hi tristan,

    you 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

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


      for 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

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

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

    ReplyDelete