Vasiljko's blog

n-th number in given list
By Vasiljko, history, 7 years ago, In English

List of integers is formed such that all integers that can be written in form 2x3y5z are sorted in increasing order. So, list look like this: 1, 2, 3, 4, 5, 6, 8, 9, ... What is n-th element (0-indexed) in list?
0 <  = n <  = 105

Input
500
Output
944784

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Am I missing anything, or answer for 500 is 937500?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is 0-indexed. for n=0 answer is 1, for n=1 answer is 2... Maybe this?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Yep, you are right. There is simple O(n) algorithm:

          intt n; cin >> n; n++;
    intt pw2 = 0, pw3 = 0, pw5 = 0, next2 = 2, next3 = 3, next5 = 5, res = 1;
    dp[0] = 1;
    for (intt i = 1; i < n; i++) {
        dp[i] = res = min (next2, min (next3, next5));
        if (next2 == res) {
            next2 = 2 * dp[pw2 + 1];
            pw2++;
        }
        if (next3 == res) {
            next3 = 3 * dp[pw3 + 1];
            pw3++;
        }
        if (next5 == res) {
            next5 = 5 * dp[pw5 + 1];
            pw5++;
        }
    }
    cout << res << endl;

      Idea is same with fofao_funk's.

      → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

Disregarding the overflow, I think this should work: create an ordered set which contains the element 1 initially. Now, you will do the following n + 1 times: pop out the smallest element X in the set (and delete it) and then put the elements 2X, 3X and 5X in the set. The n + 1-th popped element is the answer.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Shouldn't that be MLE? I don't have ML but there is high probability for that, am I right?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +6 Vote: I do not like it

      You should use O(N) memory, since for each popped element (at most N) you put 3 other in the set.

      → Reply