Leetcode Ugly Number II problem solution

YASH PAL,

In this Leetcode Ugly Number II problem solution An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. we have given an integer n, return true if nth is an ugly number.

Leetcode Ugly Number II problem solution

Problem solution in Python.

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # DP cache
        dp = [0]*n
        # DP base case
        dp[0] = 1
        # DP step case
        i2 = i3 = i5 = 0
        for i in range(1, n):
            k = min(dp[i2]*2, dp[i3]*3, dp[i5]*5) # Next ugly number
            dp[i] = k
            if dp[i] == dp[i2]*2:
                i2 = i2+1
            if dp[i] == dp[i3]*3:
                i3 = i3+1
            if dp[i] == dp[i5]*5:
                i5 = i5+1
        return dp[n-1]

Problem solution in Java.

class Solution{
public int nthUglyNumber(int n) {
    ArrayList<Integer> l= new ArrayList<>();
    l.add(1);
    int i2=0,i3=0,i5=0;
    while(l.size()<n){
        int m2 = l.get(i2)*2;
        int m3 = l.get(i3)*3;
        int m5 = l.get(i5)*5;
        int min = Math.min(m2, Math.min(m3, m5));
        l.add(min);
        if(min==m2)
            i2++;
        if(min==m3)
            i3++;
        if(min==m5)
            i5++;
    }
    return l.get(l.size()-1);
}
}

Problem solution in C++.

class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<long int, vector<long int>, greater<long int> > q;
        q.push(1);
        unordered_set<long int> walked;
        walked.insert(1);
        for(int i=0; i<n-1; i++){
            long int tmp=q.top();
            q.pop();
            if(tmp>=INT_MAX/2)continue;
            if(walked.find(tmp*2)==walked.end()){
                q.push(tmp*2);
                walked.insert(tmp*2);
            }
            if(walked.find(tmp*3)==walked.end()){
                q.push(tmp*3);
                walked.insert(tmp*3);
            }
            if(walked.find(tmp*5)==walked.end()){
                q.push(tmp*5);
                walked.insert(tmp*5);
            }
        }
        return q.top();
        
    }
};

Problem solution in C.

#define min(x,y) (x < y ? x : y)

int nthUglyNumber(int n) {
  static int arr[1691] = {[0]= 1},
  i  = 1, i2 = 0, i3 = 0, i5 = 0,
  n2 = 2, n3 = 3, n5 = 5;
  
  for (; i < n; i++) {
    arr[i] = min(min(n2, n3), n5);
    if (arr[i] == n2) n2 = 2 * arr[++i2];
    if (arr[i] == n3) n3 = 3 * arr[++i3];
    if (arr[i] == n5) n5 = 5 * arr[++i5];
  }

  return arr[n-1];
}

coding problems solutions