Ugly Number II - Medium - L
Published:
Question
- https://leetcode.com/problems/ugly-number-ii/
Given an integer n, return the nth ugly number.
Ugly number is a positive number whose prime factors only include 2, 3, and/or 5.
Approach
- power approach : Wrong because it will generate only multiple of 2 :
class Solution { public: int nthUglyNumber(int n) { int pow2 = 0; int pow3 = 0; int pow5 = 0; int ans = 1; while(n!=1) { cout<<pow2<<" "<<pow3<<" "<<pow5<<endl; long long int curr = pow(2, pow2)*pow(3, pow3)*pow(5, pow5); cout<<curr<<endl; int curr1 = 2*curr; int curr2 = 3*curr; int curr3 = 5*curr; ans = min(curr1, min(curr2, curr3)); cout<<ans<<endl; if(ans == curr1) { pow2++; } if(ans == curr2) { pow3++; } if(ans == curr3) { pow5++; } n--; } return ans; } }; - DP
Solution
class Solution {
public:
int nthUglyNumber(int n) {
if (n == 1) {
// 1 is alway ugly
return 1;
}
// Table of lenght n that stores the ugly numbers
vector<int> ugly(n, 0);
// store the 0th element with 1
ugly[0] = 1;
// idx to store the next 3 multiples
int i2 = 0;
int i3 = 0;
int i5 = 0;
// variables to store the next 3 multiples
int next_multiple_of_2 = ugly[i2] << 1;
int next_multiple_of_3 = ugly[i3] * 3;
int next_multiple_of_5 = ugly[i5] * 5;
// Fill the ugly table
for (int i = 1; i < ugly.size(); i++) {
// Find the min of 3 next multiplies and that is the ith
// ugly number
int num = std::min(next_multiple_of_2, std::min(next_multiple_of_3, next_multiple_of_5));
// store it int he ugly table
ugly[i] = num;
// update the next multiples of the 3 choices
if (num == next_multiple_of_2) {
i2++;
next_multiple_of_2 = ugly[i2] << 1;
}
if (num == next_multiple_of_3) {
i3++;
next_multiple_of_3 = ugly[i3] * 3;
}
if (num == next_multiple_of_5){
i5++;
next_multiple_of_5 = ugly[i5] * 5;
}
}
// return the last num in the ugly array
return ugly.back();
}
};