Power Of Two Solution for TCS NQT
Company: TCS NQT · Difficulty: Easy · Topics: Mathematics, Bit Manipulation
Problem Statement
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 == 2^x.
Examples
Example 1:
Input: n = 1
Output: true
Explanation: 2^0 = 1
Example 2:
Input: n = 16
Output: true
Explanation: 2^4 = 16
Example 3:
Input: n = 3
Output: false
Explanation: 3 is not a power of two.
Example 4:
Input: n = 0
Output: false
Explanation: 0 is not a power of two.
Example 5:
Input: n = 8
Output: true
Explanation: 2^3 = 8
Intuition
A number is a power of two if and only if it has exactly one bit set to 1 in its binary representation. This is because powers of 2 in binary are:
- 2^0 = 1 = 1
- 2^1 = 2 = 10
- 2^2 = 4 = 100
- 2^3 = 8 = 1000
- 2^4 = 16 = 10000
Notice that each power of 2 has exactly one '1' bit.
Approach
Approach 1: Bit Manipulation (Optimal)
1. Check if n > 0 (powers of 2 are positive)
2. Use n & (n-1) to remove the least significant bit
3. If the result is 0, then n had exactly one bit set
Approach 2: Division by 2
1. If n ≤ 0, return false
2. While n > 1, repeatedly divide by 2
3. If n becomes 1, it's a power of 2
4. If n becomes odd and > 1, it's not a power of 2
Approach 3: Logarithm
1. If n ≤ 0, return false
2. Calculate log2(n)
3. Check if the result is an integer
Approach 4: Count Set Bits
1. Count the number of set bits in n
2. If count == 1, it's a power of 2
Dry Run
Let's trace through different examples:
Example: n = 16
- Binary: 10000
- n-1 = 15, Binary: 01111
- n & (n-1) = 10000 & 01111 = 00000 = 0
- Result: true (power of 2)
Example: n = 12
- Binary: 1100
- n-1 = 11, Binary: 1011
- n & (n-1) = 1100 & 1011 = 1000 = 8
- Result: false (not power of 2)
Division Method: n = 16
- 16 ÷ 2 = 8
- 8 ÷ 2 = 4
- 4 ÷ 2 = 2
- 2 ÷ 2 = 1
- Result: true (reached 1)
Key Insights
1. Binary Pattern: Powers of 2 have exactly one '1' bit
2. Bit Manipulation: n & (n-1) removes the least significant '1' bit
3. Single Bit Check: If n & (n-1) == 0 and n > 0, n is a power of 2
4. Edge Case: 0 is not a power of 2
Edge Cases
1. n = 0: Not a power of 2
2. n = 1: 2^0 = 1, so it is a power of 2
3. Negative numbers: Not powers of 2
4. Large numbers: Handle overflow carefully
Time and Space Complexity
- Time Complexity: O(1) for bit manipulation, O(log n) for division
- Space Complexity: O(1) for all approaches