1ms java solution


  • 9
    N

    Traditional solution to this problem is :

    calculate the sum of the square of each digit until it is equal to 1 or has a recurrence

    However,there is no need to calculate the sum every time.

    As we all know,

    1. each digit's range is [0,9]

    2. the range of Integer is [0,2^31-1],that is [0,10] in number of digits

    which means the square sum of each digit would always be in range[0 , 9 * 9 * 10) or [0 , 810)

    to speed up our processing,we can pre-calculate the happy numbers in range[0. 810)
    ,

    and store them in our program for later lookups

    Here is my implementation:

    //this is the bitset representation of happy numbers in range[0,810)
    private static final long[]happyMark = new long[]{580548859274370L, 35812649762896L, 
                              5764889547766761510L, 158621866461187L, -9061136725337702208L, 
                             -8574391826910016959L, 4683743612499927428L, 286423854940160L, 
                              29290989780729856L, 7566260683533189120L, 1170945809492058640L, 
                              720593571220033568L, 292095590400L};  
    
    public boolean isHappy(int n) {
        if( n>810 ){
            int sum = 0, remainder = 0;
            while( n>0 ){
                remainder = n%10;
                sum += remainder*remainder;
                n /= 10;
            }
            n = sum;
        }
        int idx = ( n>>6 );
        long bitRep = ( 1L<< (n&0x3f) );
        return ( happyMark[idx]&bitRep )!=0;
    }

  • 0
    D

    I dig! Like the idea and non traditional approach


  • 1
    M

    May you please elaborately explain the idea? Thanks!


  • 0
    N

    The whole idea is to put all happy numbers between 0 and 810 into program which could be used to directly check whether the input is a happy number instead of multiple trial and errors.

    In my implementation , i just borrow the idea of java.util.BitSet to store and search number efficiently

    As for the number "810", i think i have explained the reason quite clearly before.

    I could explain better if you specifically point out which part you dont get


  • 0
    M

    Hi newdive, thanks for your reply. I'm new to bitest and bit operations. I've done some search but haven't found a good tutorial which covers some things in your code. Below lists my questions:

    1. How to generate the happyMark array mathematically?
    2. Why n>>6 means the index in the happyMark array?
    3. Why 1L << (n&0x3f) is the bit representation of n?

    Thanks!


  • 0
    N

    Well, to know how bitset works, just dive into the source code.

    This also apply to others in the open source world, it is the most direct way to get to those ideas.

    Considering your situation, I would like to give you some hints.

    1. a 'long' has 64 bits, if we take the lowest bit as number 0, then the higest bit would represent as 63. So the whole 'long' could represent the range [0, 63].

    for example, 0x1 means you only mark at 0 position, 0x3 means you mark at 0 and 1 position, and so forth

    1. base on hint 1, you could use multiple 'long' to represent numbers in bigger range.
      if we take n 'long', then we could represent range [0, n * 64 - 1] with the k th 'long' represent numbers in range [ k * 64, k * 64 + 63 ] (k starts from 0 ).
      so for a given number t, it will be represented by the (t/64)th 'long' at (t%64)th bit

    2. n>>6 == n/64, n&0x3f == n%64 ; the left-side ones are more efficient.
      But if you find it confusing, you can just replace with n/64 and n%64 for better understanding.


  • 0
    O

    Hi, newdive, I still don't know how you got the happMark and how it works, could you tell me about that?


  • 1
    N

    Well, for better understanding, let's do some simple task first.
    Go from number 1 to 64, mark '1' when it is a happy number, otherwise mark as '0'
    happy numbers in range[0, 63] is: 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49.
    So it goes like this(it's a bit narrow here, so i divide it in half)

    1. mark happy number in range [63, 32]

        0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1

                                                  ...49...         44...                                32
    2. mark happy number in range [31, 0]

        1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0

       31...  28...         23...      19...            13...  10...     7...              1


      combine 1) and 2) together ,we get this 01 sequence:

      00000000000000100001000000000001 1001000010001000010010010000010

      If we take this as a number of 64 bit in binary form, that is 580548859274370L, our first element in the happyMark array

    Likewise, we can use this method to easily mark the rest happy numbers.

    After that we get the following marks:

    happyMark[0] = 580548859274370L           [0, 63]

    happyMark[1] = 35812649762896L             [64, 127]

    happyMark[2] = 5764889547766761510L   [128, 191]

    happyMark[3] = 158621866461187L           [192, 255]

    ... and so on

    from the above ,we can see that happyMark[i] can mark happy numbers in range[i * 64, i * 64+63].
    So given a number num, it is marked by happyMark[num/64] with its (num%64)th bit.

    check java.util.BitSet and happy number for futher understanding


  • 0
    O

    brilliant! Thank you


Log in to reply
 

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