The Power of Two
Given an integer $n$, return true if it is a power of two. Solve using a single Bit Manipulation operation ($O(1)$).
Why Interviewers Ask This
Interviewers at Uber ask this to evaluate a candidate's ability to optimize for performance and memory efficiency. They specifically test knowledge of binary representation, as Bit Manipulation is critical in high-throughput systems like ride-matching algorithms where O(1) operations reduce latency significantly.
How to Answer This Question
1. Clarify constraints immediately: Confirm if n can be negative or zero, noting that powers of two must be positive integers. 2. Propose the brute force solution first to show baseline understanding, then pivot to the optimal approach. 3. Explain the bit pattern: Powers of two have exactly one bit set (e.g., 8 is 1000). Subtracting 1 flips all bits after that single bit (7 becomes 0111). 4. Derive the logic: The bitwise AND of n and n-1 will always be zero for powers of two because they share no set bits. 5. Validate edge cases: Explicitly mention that n=0 fails this check since 0 & -1 equals 0, requiring an additional 'n > 0' condition. This demonstrates rigorous thinking aligned with Uber's focus on robust engineering.
Key Points to Cover
- Recognizing that powers of two have exactly one bit set in binary
- Deriving the n & (n-1) == 0 property through logical deduction
- Handling the specific edge case where n equals zero
- Ensuring the solution meets the strict O(1) time complexity requirement
- Connecting the algorithmic optimization to real-world system performance needs
Sample Answer
To solve this efficiently in O(1) time without loops, I'd leverage the unique properties of binary numbers. First, we must handle the edge case where n is less than or equal to zero, as powers of two are strictly positive. For any positive integer that is a power of two, its binary representation contains exactly one bit set to 1. For example, 8 is 1000 in binary. If we subtract 1 from it, we get 7, which is 0111. Notice how every bit to the right of the original set bit has flipped. When we perform a bitwise AND operation between n and n-1, the result is always zero for powers of two because there are no overlapping set bits. However, this logic also returns zero for n=0, so our final condition must be n > 0 AND (n & (n - 1)) == 0. This approach avoids iteration entirely, ensuring constant time complexity, which is vital for high-frequency trading or real-time matching systems where Uber operates. It shows deep understanding of hardware-level optimizations rather than just writing functional code.
Common Mistakes to Avoid
- Forgetting to check if n is greater than zero, leading to false positives for n=0
- Using a loop to divide by two repeatedly, which results in O(log n) instead of O(1)
- Attempting to use logarithms with floating-point arithmetic, risking precision errors
- Failing to explain the binary logic behind the bit manipulation trick during the interview
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.