Ugly Number II LeetCode Solution

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

Problem Statement

Ugly Number II LeetCode Solution – 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.

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 2, 3 or 5. So, let starts be the indexes of ugly numbers, that when multiplied by 2, 3 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 »