I can't figure out why my code gets wrong at 1548


  • 0
    D
    public int nthUglyNumber(int n){
            if (n == 1){
                return 1;
            }else {
                int[] memo = new int[n + 1];
                for (int i = 0; i <= n; i++) {
                    memo[i] = Integer.MAX_VALUE;
                }
                memo[1] = 1;
                memo[2] = 2;
                for (int i = 2; i <= n-1; i++) {
                    for (int j = 1; j < i; j++) {
                        if (memo[j] * 2 > memo[i]) {
                            memo[i+1] = Math.min(memo[j] * 2, memo[i+1]);
                        }
                        if (memo[j] * 3 > memo[i]) {
                            memo[i+1] = Math.min(memo[j] * 3, memo[i+1]);
                        }
                        if (memo[j] * 5 > memo[i]) {
                            memo[i+1] = Math.min(memo[j] * 5, memo[i+1]);
                        }
                    }
                }
                return memo[n];
            }
        }
    

    this code work well in previous 1547 numbers but get wrong since 1548, can someone help me figure what's the problem?


  • 1
    Z

    Because actually the 1548th ugly number is bigger than Integer.MAX_VALUE


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.