tricky way to find out Ugly Number(at LeetCode)

For the given question in LeetCode.com, https://leetcode.com/problems/ugly-number/

I coded kind of tricky logic to solve this question.

Ugly number is number which is only divided by three prime numbers; 2, 3, 5 (1 is considered as Ugly Number)

At first, I tried this and got time limit error.

    bool isUgly(int num) {
        if(num == 1) return true;
        do{
            if(num % 2 == 0) { num /= 2; continue; }
            if(num % 3 == 0) { num /= 3; continue; }
            if(num % 5 == 0) { num /= 5; continue; }
            if(num == 1) return true;
            return false;
        } while(1);
    }

Well, if very big number is given, there might be lots of loop.


So I added one line below and I got Accepted with 8 msec runtime.

if(num % 7 == 0) { return false; }

Fine, but unsatisfied because someone got faster result.

So I added more conditions and final code is this:

    bool isUgly(int num) {
        if(num == 1) return true;
        do{
            if(num % 7 == 0) { return false; }
            else if(num % 11 == 0) { return false; }
            else if(num % 13 == 0) { return false; }
            else if(num % 17 == 0) { return false; }
            else if(num % 19 == 0) { return false; }
            else if(num % 23 == 0) { return false; }

            if(num % 2 == 0) { num /= 2; continue; }
            if(num % 3 == 0) { num /= 3; continue; }
            if(num % 5 == 0) { num /= 5; continue; }
            
            if(num == 1) return true;
            return false;
        } while(1);
        
        
    }

Finally I got Accepted with 4 msec runtime.

Heh, lucky.

This code might be silly like a undergraduate student's job but shows good performance for the LeetCode examples.

I don't know how big numbers should be evaluated for the Ugly Number but most numbers might have small prime factors like 2, 3, 5, 7, 11, 13 blar blar..

I am not a mathematician and I cannot speculate the way of getting prime factors effectively.

However, If you just divide the given number with few prime numbers such as 7, 11, 13 ... 23, you can quickly make it.

According to Wikipedia, the number of prime numbers below a given number is approximately like this: 

boost::shared_ptr Assertion `px != 0' failed.

a.out: /usr/local/include/boost/smart_ptr/shared_ptr.hpp:653: typename boost::detail::sp_member_access<T>::type boost::shared_ptr<T>::operator->() const [with T = classA, typename boost::detail::sp_member_access<T>::type = classA*]: Assertion `px != 0' failed.


When this assertion comes to me, this is because assigned object to the shared_ptr is NULL.

See sample code below.

#include <boost/shared_ptr.hpp>
#include <iostream>

class classA{
private:
    int number_;
public:
    classA(){ number_ = 1;}
public:
    int number() { return number_; }
};

typedef boost::shared_ptr<classA> classA_Ptr;

void makeNull(){
    std::cout << "@sshtel @@@@@@@@@ start function" << std::endl;

    classA_Ptr ap1(new classA());
    std::cout << "@sshtel @@@@@@@@@ ap1:" << ap1->number() <<  std::endl;

    classA *ca = 0;
    classA_Ptr ap2(ca);
    std::cout << "@sshtel @@@@@@@@@ ap2:" << ap2->number() <<  std::endl;

    std::cout << "@sshtel @@@@@@@@@ end of function" << std::endl;
}

int main(){
    makeNull();
    return 0;
}

-----------------------------------------------------------------------------

sshtel@rnd4svr4:~/test/SharedPtr$ ./a.out
@sshtel @@@@@@@@@ start function
@sshtel @@@@@@@@@ ap1:1
a.out: /usr/local/include/boost/smart_ptr/shared_ptr.hpp:653: typename boost::detail::sp_member_access<T>::type boost::shared_ptr<T>::operator->() const [with T = classA, typename boost::detail::sp_member_access<T>::type = classA*]: Assertion `px != 0' failed.
Aborted
sshtel@rnd4svr4:~/test/SharedPtr$

-----------------------------------------------------------------------------

To avoid this dangerous situation, you should check memory result of object allocation every time.

boost::shared_ptr<CLASS> c_ptr;
CLASS *c;
try{
    c = new CLASS();

    c_ptr.reset(c);
}
catch(std::bad_alloc){
    // exception
}

Reason why you must not call function in condition

you cannot guarantee all functions are going to be called in condition.
See code below...

 #include <stdio.h>  
 int funcA(){  
   printf("funcA \n");  
   return 0;  
 }  
 int funcB(){  
   printf("funcB \n");  
   return 1;  
 }  
 int main()  
 {  
   int a = 0;  
   int b = 1;  
   if( funcA() || funcB() )  
   {  
     printf("first condition! funcA() || funcB() \n\n");  
   }  
   if( funcB() || funcA() ){  
     printf("second condition! funcB() || funcA() \n\n");  
   }  
   if( funcA() && funcB() )  
   {  
     printf("third condition! funcA() && funcB() \n\n");  
   }  
   if( funcB() && funcA() ){  
     printf("fourth condition! funcB() && funcA() \n\n");  
   }  
   return 0;  
 }  

funcA
funcB
first condition! funcA() || funcB()

funcB
second condition! funcB() || funcA()

funcA
funcB
funcA



* if the function calls are related to I/O, you may make a mistake and cause memory leak.