hr47

Ugly Number Sequel

Jun 16th, 2021 (edited)
245
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int solve(int n) {
  2.     if(n<6){
  3.         return n+1;
  4.     }
  5.  
  6.     vector<bool> dp(n+1);
  7.     dp[0]=false;
  8.     dp[1]=dp[2]=dp[3]=dp[4]=dp[5]=true;
  9.    
  10.     int i=6,j=5,ans;
  11.     while(j!=n+1){
  12.         if((i%2==0 && dp[i/2]==true)||(i%3==0 && dp[i/3]==true) ||(i%5==0 && dp[i/5]==true)){
  13.             dp[i]=true,ans=i,j++;
  14.         }
  15.         else{
  16.             dp[i]=false;
  17.         }
  18.         i++;
  19.     }
  20.     return ans;
  21. }
RAW Paste Data