Vasiljko's blog

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?

  • »
    »
    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?

    • »
      »
      »
      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.

»
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.

  • »
    »
    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?

    • »
      »
      »
      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.