#3 Leetcode 231 Power of Two

tags:Recursion iteration bit manipulation easy leetcode

Issue

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

Sample Input & Output

Input: n = 1
Output: true
Explanation: 20 = 1

Input: n = 16
Output: true
Explanation: 24 = 16

Input: n = 3
Output: false

Constraints

• -2^31 <= n <= 2^31 - 1.

Follow up

Could you solve it without loops/recursion?

• Solution Bit manipulation

Solutions

Most voted

Recrusion

/**
 * Time complexity would be O(logn).
 * Space complexity would be O(logn).
 */

var isPowerOfTwo = function(n) {
    if (n < 1) return false;
    if (n === 1) return true;
    return isPowerOfTwo(n/2);
};

Iteration

https://leetcode.com/problems/power-of-two/discuss/2403463/Javascript-Solution

/**
 * Time complexity would be O(logn).
 * Space complexity would be O(logn).
 */

var isPowerOfTwo = function(n) {
    if(n<1) return false;
    if(n === 1) return true;
    while(n !== 1 ) {
        let x = n/2;
        if(x % 2 !== 0 && x > 1) return false;
        n/=2;
    }
    return true;
};

Bit manipulation

https://leetcode.com/problems/power-of-two/discuss/369024/100-fastest-0ms-one-line-solution-with-explanation-binary-trick

/**
 * Time complexity would be O(1).
 * Space complexity would be O(1).
 */

var isPowerOfTwo = function(n) {
    return n => n > 0 ? !(n & n-1) : false;
};

Everyone's

東

// Time O(log(n)) | Space O(log(n)); where n is the input number
var isPowerOfTwo = function(n) {
    if (n < 1) return false;
    else if (n === 1) return true;
    else if (Number.isInteger(n/2)) return isPowerOfTwo(n/2)
    else return false;
};

Hao

/**
 * Time complexity would be O(logn).
 * Space complexity would be O(logn).
 */

var isPowerOfTwo = function(n) {
    if (n < 1) return false;
    if (n === 1) return true;
    return isPowerOfTwo(n/2);
};

YC

/**
 * time: O(log n)
 * space: O(log n)
 */
var isPowerOfTwo = function(n) {
    if(n === 0) return false;
    if(n === 1) return true;
    if(n % 2 === 1) return false;
    return isPowerOfTwo(n/2);
};

Becky

月薪

// Time O(？) Space O(？)
var isPowerOfTwo = function(n) {
    if(n !== 0){
        if(n === 1) return true;
        if(!!n % 2) return isPowerOfTwo(n / 2);
    }
    return false;
};

Discussion

Bit manipulation

Negative binary representation system

Link

How to represent number with the same absolute value but different sign?

+ 00000001 # +1
- 00000001 # -1

Sign Magnitude

• Use the Most Significant Bit (MSB), the leftmost bit in a number, to represent the sign.
• Only 7 bits remain for magnitude.
• Normally an 8 bit value would have the range of 0 to 255. The range of a signed 8 bit number is now -127 to 127 because the value of magnitude here (0000001) is still the same, which could cause error when we adding and subtracting values.

0 0000001 # +1
1 0000001 # -1

One's Complement

• When representing negative numbers, you invert all the bits. The 1's become 0's and the 0's become 1's.
• Because the range of the system is -127 to 127, it has the same issue which Sign Magnitude system faces.

0 0000001 # +1
1 1111110 # -1

Two's Complement

• Two's complement is much more widely used, including Javascript, than one's complement.
• Like One's Complement, We first invert the bits, but the different things here is that we would then add one.

Example to find negative two's complement numbers

Numbers and binary addition

Steps

1. Find the positive binary value for the negative number you want to represent.
2. Add a 0 to the front of the number, to indicate that it is positive.
3. Invert or find the complement of each bit in the number.
4. Add 1 to this number.

Let's find -1

1 = 001
Adding 0 to the front becomes 0001
'Inverted' becomes 1110
Add 1 = 1111 (-8 + 4 + 2 + 1 = -1)

• Signed two's complement number has a range of -128 to 127. Unlike one's complement and sign magnitude, two's complement does not have addition and subtraction problems.

0 0000001 # +1
1 1111111 # -1

Bitwise Operations

W3school/JavaScript Bitwise Operations