[sword finger offer] 49 Ugly number

The finger of the sword Offer 49. Ugly number

subject

  We will include only qualitative factors 2、3 and 5 The number of is called ugly （Ugly Number）. Seek the order from small to large n Ugly number .

Ideas

  Ugly numbers contain only factors 2,3,5, So there is “ Ugly number = Some clown number x Some factor ”

  Ugly number Xn+1 It can only be one of the following three cases ：
* Xn+1 = Xa * 2
* Xn+1 = Xb * 3
* Xn+1 = Xc * 5

Ugly number recurrence formula ： The next ugly number is the minimum of these three cases ：

Xn+1 = min(Xa x 2,Xb x 3, Xc x 5)

Code

class Solution {
    
public:
    int nthUglyNumber(int n) {
    
        int a = 0,b = 0,c = 0;
        int dp[n];
        dp[0] = 1;

        for(int i = 1; i < n; i++)
        {
    
            int n2 = dp[a] * 2;
            int n3 = dp[b] * 3;
            int n5 = dp[c] * 5;
            dp[i] = min(min(n2,n3),n5);

            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;

        }
        return dp[n - 1];
    }
};