C# Solution by calculating the range of possible factors


  • 0
    L
    public int NthUglyNumber(int n) {
        int[] ugly = new int[Math.Max(5, n)];
        ugly[0] = 1; ugly[1] = 2; ugly[2] = 3; ugly[3] = 4; ugly[4] = 5;
        for(int i = 5; i < n; i++){
            int j = i, k = i, min = int.MaxValue;
            while(j >= 0 && (2 * (long)ugly[j - 1]) > ugly[i - 1]) j--;
            while(k >= 0 && (5 * (long)ugly[k - 1]) > ugly[i - 1]) k--;
            for(;k <= j; k++){
                if(ugly[k] * 2 > ugly[i - 1]) min = Math.Min(min, ugly[k] * 2);
                if(ugly[k] * 3 > ugly[i - 1]) min = Math.Min(min, ugly[k] * 3);
                if(ugly[k] * 5 > ugly[i - 1]) min = Math.Min(min, ugly[k] * 5);
            }
            ugly[i] = min;
        }
        return ugly[n - 1];
    }

Log in to reply
 

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