Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/231.html

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.

 

Example 1:

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

Example 2:

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

Example 3:

Input: n = 3
Output: false

 

Constraints:

  • -231 <= n <= 231 - 1

 

Follow up: Could you solve it without loops/recursion?

Algorithm

Observe the characteristics of the binary notation of the power of 2:

1   2   4       8       16   ....

1   10  100     1000    10000 ...

The power of 2 has only one 1, and the rest is 0s, so our problem-solving idea is to determine whether the lowest bit is 1 each time, then shift to the right, and finally count the number of 1s to determine whether it is Power of 2

Code

  • 
    public class Power_of_Two {
    
    
        class Solution {
            public boolean isPowerOfTwo(int n) {
                int cnt = 0;
                while (n > 0) {
                    cnt += (n & 1);
                    n >>= 1;
                }
                return cnt == 1;
    
            }
        }
    }
    
    ############
    
    class Solution {
        public boolean isPowerOfTwo(int n) {
            return n > 0 && (n & (n - 1)) == 0;
        }
    }
    
  • // OJ: https://leetcode.com/problems/power-of-two/
    // Time: O(1)
    // Space: O(1)
    class Solution {
    public:
        bool isPowerOfTwo(int n) {
            if (n <= 0) return false;
            while ((n & 1) == 0) n >>= 1;
            return n == 1;
        }
    };
    
  • class Solution:
        def isPowerOfTwo(self, n: int) -> bool:
            return n > 0 and (n & (n - 1)) == 0
    
    ############
    
    class Solution(object):
      def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n != 0 and (n & -n) == n
    
    
  • func isPowerOfTwo(n int) bool {
    	return n > 0 && (n&(n-1)) == 0
    }
    
  • function isPowerOfTwo(n: number): boolean {
        return n > 0 && (n & (n - 1)) == 0;
    }
    
    
  • /**
     * @param {number} n
     * @return {boolean}
     */
    var isPowerOfTwo = function (n) {
        return n > 0 && (n & (n - 1)) == 0;
    };
    
    

All Problems

All Solutions