I am trying to solve a problem on leetcode.com Ugly Number II.

problem: An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

example:

Input: n = 10 Output: 12 Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

This is my solution

class Solution {
    public int nthUglyNumber(int n) {
      int outputNumber = 6;
            int temp = 1;

            if(n<7){return n;}
            int i = 7;
                     while (i !=(n 1)) {
                     outputNumber = outputNumber   1;
                     temp = outputNumber;

                     while(temp%5==0){temp=temp/5;}
                     while(temp%2==0){temp=temp/2;}

                      while(temp%3==0){temp=temp/3;}



                      if(temp==1) {
                          i=i 1;
                      }
                    }
            return outputNumber;
    }
}

this works for small numbers, but when the input is a big number, then I have Time Limit Exceeded The question is how to optimize this code?

Thank you!

CodePudding user response：

Hint: You're looking for numbers of the form

for non-negative integers . Instead, of looking for ugly numbers, wouldn't it be easier to just generate them?

CodePudding user response：

I used two tricks to make it about twice as fast, but it's still far too slow. I suspect the check-all-integers-for-ugliness approach is hopeless, and you'll find faster approaches in the discussions on LeetCode.

class Solution {
    public int nthUglyNumber(int n) {
        for (int i = 1; true; i  )
            if (1418776204833984375L % (i / (i & -i)) == 0)
                if (--n == 0)
                    return i;
    }
}

The two tricks:

• i & -i extracts the lowest 1-bit, so dividing by that takes out every factor 2.
• 1418776204833984375 is 3¹⁹×5¹³. Every positive int with only factors 3 and 5 divides that, and every other positive int doesn't.