Q61 Ugly Number 2 - LeetCode 264
Sun Apr 02 2023 08:10:47 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public boolean isUgly(int n) {
/* Q61 dp playlist , every cell denote ith ugly number . we make 3
pointers for 2,3,5 keeping every pointer at 1 . we traverse the dp and
find next ugly number by multiplying prev ugly number by all 3 factors
and taking minimum of all and moving pointer which gave minimum value by
1.
-> if more than 1 pointer gives the same minimum value we both all such
pointers by 1
*/
if(n == 1)return true;
int[] dp = new int[n+1];
dp[1] = 1; //1 is 1st ugly number
int f2 = 1 , f3 = 1 , f5 = 1;
for(int i = 2 ; i <= n ; i++){
int val2 = 2 * dp[f2] , val3 = 3 * dp[f3] , val5 = 5 * dp[f5];
//ugly number will be min of all vals
dp[i] = Math.min(val2 , Math.min(val3,val5));
//updating pointers
if(dp[i] == val2) f2++;
if(dp[i] == val3) f3++;
if(dp[i] == val5) f5++;
//if before reaching n
if(dp[i] == n)
return true;
// else if(dp[i] > n)
// return false;
}
for(int i = 0 ;i < n ; i++)
System.out.print(dp[i] + " ");
return false;
}
}
content_copyCOPY
https://leetcode.com/problems/ugly-number-ii/
Comments