Interesting bounds about this problem


  • 3
    L
    1. Actually, the input space is much smaller than expected if we insist an int range output.
      When input n is greater than 1691, the output overflows the int range.
    2. Another way to view this bound is that all ugly numbers must be in the form 2^a*3^b*5^c. Since we have log2(Integer.MAX_VALUE)=a<31, log3(Integer.MAX_VALUE)=b<20 and log5(Integer.MAX_VALUE)=c<14, the combination allowed is surely under 31*20*14~=8400.

    So ugly number is sparser than one would usually think, and please do take care of overflow.


  • 0
    D

    @lcn interesting observation.


Log in to reply
 

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