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; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter