4 different ways to solve -- Iterative / Recursive / Bit operation / Math


  • 48
    M

    This question is not an difficult one, and there are many ways to solve it.

    Method 1: Iterative

    check if n can be divided by 2. If yes, divide n by 2 and check it repeatedly.

    if(n==0) return false;
    while(n%2==0) n/=2;
    return (n==1);
    

    Time complexity = O(log n)

    Method 2: Recursive

    return n>0 && (n==1 || (n%2==0 && isPowerOfTwo(n/2)));
    

    Time complexity = O(log n)

    Method 3: Bit operation

    If n is the power of two:

    • n = 2 ^ 0 = 1 = 0b0000...00000001, and (n - 1) = 0 = 0b0000...0000.
    • n = 2 ^ 1 = 2 = 0b0000...00000010, and (n - 1) = 1 = 0b0000...0001.
    • n = 2 ^ 2 = 4 = 0b0000...00000100, and (n - 1) = 3 = 0b0000...0011.
    • n = 2 ^ 3 = 8 = 0b0000...00001000, and (n - 1) = 7 = 0b0000...0111.

    we have n & (n-1) == 0b0000...0000 == 0

    Otherwise, n & (n-1) != 0.

    For example, n =14 = 0b0000...1110, and (n - 1) = 13 = 0b0000...1101.

    return n>0 && ((n & (n-1)) == 0);
    

    Time complexity = O(1)

    Method 4: Math derivation

    Because the range of an integer = -2147483648 (-2^31) ~ 2147483647 (2^31-1), the max possible power of two = 2^30 = 1073741824.

    (1) If n is the power of two, let n = 2^k, where k is an integer.

    We have 2^30 = (2^k) * 2^(30-k), which means (2^30 % 2^k) == 0.

    (2) If n is not the power of two, let n = j*(2^k), where k is an integer and j is an odd number.

    We have (2^30 % j*(2^k)) == (2^(30-k) % j) != 0.

    return n>0 && (1073741824 % n == 0);
    

    Time complexity = O(1)


  • 0
    E

    clear explanations and examples


  • 0

    I really like the third one


  • 0
    Z

    the fourth one is interesting.
    But I think the step 2 seems not so necessary.
    Besides, if n is a prime number, n can't be represented by j*(2^k);


Log in to reply
 

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