Interesting bounds about this problem

  • 3
    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

    @lcn interesting observation.

Log in to reply

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