Ugly Number II LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Citadel Facebook Google MicrosoftViews 3688

Problem Statement

Ugly Number II LeetCode Solution – An ugly number is a positive integer whose prime factors are limited to 23, and 5.

Given an integer n, return the nth ugly number.

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.

Explanation

We have an array k of the first n ugly number. We only know, in the beginning, the first one, which is 1. Then

k[1] = min( k[0]x2, k[0]x3, k[0]x5). The answer is k[0]x2. So we move 2’s pointer to 1. Then we test:

k[2] = min( k[1]x2, k[0]x3, k[0]x5). And so on. Be careful about the cases such as 6, in which we need to forward both pointers of 2 and 3.

x here is multiplication.

Approach

Let us solve this problem for the general case: that is not only for 2,3,5 divisors, but for any of them and any number of them. factors = [2,3,5] and k=3 in our case.
Let Numbers be an array, where we keep all our ugly numbers. Also, note, that any ugly number is some other ugly number, multiplied by 23 or 5. So, let starts be the indexes of ugly numbers, that when multiplied by 23 or 5 respectively, produces the smallest ugly number that is larger than the current overall maximum ugly number. Let us do several first steps to understand it better:

  1. starts = [0,0,0] for numbers 2,3,5, so new_num = min(1*2,1*3,1*5) = 2, and now starts = [1,0,0]Numbers = [1,2].
  2. starts = [1,0,0], so new_num = min(2*2,1*3,1*5) = 3, and now starts = [1,1,0]Numbers = [1,2,3].
  3. starts = [1,1,0], so new_num = min(2*2,2*3,1*5) = 4, so now starts = [2,1,0]Numbers = [1,2,3,4].
  4. starts = [2,1,0], so new_num = min(3*2,2*3,1*5) = 5, so now starts = [2,1,1]Numbers = [1,2,3,4,5].
  5. starts = [2,1,1], so new_num = min(3*2,2*3,2*5) = 6, so let us be careful in this case: we need to increase two numbers from start, because our new number 6 can be divided both by 2 and 3, so now starts = [3,2,1]Numbers = [1,2,3,4,5,6].
  6. starts = [3,2,1], so new_num = min(4*2,3*3,2*5) = 8, so now starts = [4,2,1]Numbers = [1,2,3,4,5,6,8]
  7. starts = [4,2,1], so new_num = min(5*2,3*3,2*5) = 9, so now starts = [4,3,1]Numbers = [1,2,3,4,5,6,8,9].
  8. starts = [4,3,1], so new_num = min(5*2,4*3,2*5) = 10, so we need to update two elements from starts and now starts = [5,3,2]Numbers = [1,2,3,4,5,6,8,9,10]
  9. starts = [5,3,2], so new_num = min(6*2,4*3,3*5) = 12, we again need to update two elements from starts, and now starts = [6,4,2]Numbers = [1,2,3,4,5,6,8,9,10,12].
  10. starts = [6,4,2], so new_num = min(8*2,5*3,3*5) = 15, we again need to update two elements from starts, and now starts = [6,5,3]Numbers = [1,2,3,4,5,6,8,9,10,12,15].

Code

C++ Code For Ugly Number II

class Solution {
public:
    int nthUglyNumber(int n) {
        if(n <= 0) return false; // get rid of corner cases 
        if(n == 1) return true; // base case
        int t2 = 0, t3 = 0, t5 = 0; //pointers for 2, 3, 5
        vector<int> k(n);
        k[0] = 1;
        for(int i  = 1; i < n ; i ++)
        {
            k[i] = min(k[t2]*2,min(k[t3]*3,k[t5]*5));
            if(k[i] == k[t2]*2) t2++; 
            if(k[i] == k[t3]*3) t3++;
            if(k[i] == k[t5]*5) t5++;
        }
        return k[n-1];
    }
};

Java Code For Ugly Number II

public class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        for(int i=1;i<n;i++){
            int min = Math.min(Math.min(factor2,factor3),factor5);
            ugly[i] = min;
            if(factor2 == min)
                factor2 = 2*ugly[++index2];
            if(factor3 == min)
                factor3 = 3*ugly[++index3];
            if(factor5 == min)
                factor5 = 5*ugly[++index5];
        }
        return ugly[n-1];
    }
}

Python Code For Ugly Number II

class Solution:
    def nthUglyNumber(self, n):
        factors, k = [2,3,5], 3
        starts, Numbers = [0] * k, [1]
        for i in range(n-1):
            candidates = [factors[i]*Numbers[starts[i]] for i in range(k)]
            new_num = min(candidates)
            Numbers.append(new_num)
            starts = [starts[i] + (candidates[i] == new_num) for i in range(k)]
        return Numbers[-1]

Complexity Analysis for Ugly Number II LeetCode Solution

Time Complexity

O(N)

Space Complexity

O(N)

Reference: https://en.wikipedia.org/wiki/Factor

Translate »