Why my code fails for any input beyond 1500?


  • 0
    M

    class Solution {
    public:
    bool isUgly(int n)
    {
    if(n==0) return false;
    while(n%2==0) n=n/2;
    while(n%3==0) n=n/3;
    while(n%5==0) n=n/5;
    if(n==1) return true;
    return false;

    }
    void generateuglyno(std::map<int,int> &n,int cnt)
    {
        n[1]=1;
        int var=0;
        std::map<int,int>::iterator it = n.begin();
        do
        {
            n[(it->first)*2] = 1;
            n[(it->first)*3] = 1;
            n[(it->first)*5] = 1;
            it++;
    
            if(n.size()>cnt)
            {
                std::map<int,int>::iterator it2 = n.begin();
                std::advance(it2,cnt-1);
                var = it2->first;
                if(((it->first)*2)>var)
                    cnt =0;
            }
        }while(cnt);
    
    }
    int nthUglyNumber(int n) {
        int i=0;
        std::map<int,int> n1;
        generateuglyno(n1,n);
    
        std::map<int,int>::iterator it = n1.begin();
        std::advance(it,n-1);
        return it->first;
        
    }
    

    };


  • 1
    Z

    You can not use int to store ugly number when the number is big.

    The 1547th ugly number is bigger than the range of unsigned int.

    And even at 1400, the 5*ugly number is overflow and you map get this negative number so your code failed.

    I think you might change your map and i to long long int and try again^_^


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.