Binary Number with Alternating Bits
EasyPrompt
Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.
Example 1:
Input: n = 5
Output: true
Explanation: The binary representation of 5 is: 101Example 2:
Input: n = 7
Output: false
Explanation: The binary representation of 7 is: 111.Example 3:
Input: n = 11
Output: false
Explanation: The binary representation of 11 is: 1011.
Constraints:
1 <= n <= 231 - 1
Approaches
3 approaches with complexity analysis and trade-offs.
This approach converts the integer into its binary string representation. Then, it iterates through the string to check if any two adjacent characters (bits) are the same. If it finds such a pair, the number does not have alternating bits. If the entire string is traversed without finding such a pair, the bits are alternating.
Algorithm
- Convert the input integer
nto its binary string representation usingInteger.toBinaryString(n). - Loop through the binary string from the second character (index 1) to the end.
- In each iteration, compare the current character
s.charAt(i)with the previous characters.charAt(i-1). - If
s.charAt(i) == s.charAt(i-1), it means two adjacent bits are the same. Returnfalseimmediately. - If the loop completes without returning, it means all adjacent bits were different. Return
true.
Walkthrough
This is the most straightforward approach. We first convert the number into a sequence of characters representing its bits and then perform a simple linear scan to check for the alternating property.
class Solution { public boolean hasAlternatingBits(int n) { String binaryString = Integer.toBinaryString(n); for (int i = 1; i < binaryString.length(); i++) { if (binaryString.charAt(i) == binaryString.charAt(i - 1)) { return false; } } return true; }}Complexity
Time
O(log n). The number of bits in `n` is proportional to log₂(n). Converting the number to a string and iterating through it both take time proportional to the number of bits.
Space
O(log n). We need to store the binary string representation of `n`, which requires space proportional to the number of bits.
Trade-offs
Pros
Simple to understand and implement.
Leverages built-in language features for number-to-string conversion.
Cons
Less efficient in terms of both time and space compared to bit manipulation approaches.
Incurs overhead from string object creation and character access.
This method avoids the overhead of string conversion by directly examining the bits of the integer. It iteratively checks the last bit, then right-shifts the number to examine the next bit, comparing each new bit with the previous one.
Algorithm
- Extract the least significant bit (LSB) of
nusing a bitwise AND operation (n & 1). Store this aslastBit. - Right-shift
nby one position (n >>= 1) to discard the LSB. - Enter a loop that continues as long as
nis greater than 0. - Inside the loop, extract the new LSB (
currentBit = n & 1). - Compare
currentBitwithlastBit. If they are equal, returnfalse. - Update
lastBittocurrentBitfor the next iteration. - Right-shift
nby one again (n >>= 1). - If the loop finishes, it means all adjacent bits were alternating, so return
true.
Walkthrough
By working directly with the integer's binary representation, we can achieve better performance, especially in terms of space. We use bitwise operators (& and >>) to inspect each bit one by one from right to left.
class Solution { public boolean hasAlternatingBits(int n) { int lastBit = n & 1; n >>= 1; while (n > 0) { int currentBit = n & 1; if (currentBit == lastBit) { return false; } lastBit = currentBit; n >>= 1; } return true; }}Complexity
Time
O(log n). The loop runs once for each bit in the number `n`. The number of bits is approximately log₂(n).
Space
O(1). This approach uses only a few variables to store the current and last bits, resulting in constant extra space.
Trade-offs
Pros
More efficient than the string conversion method, especially in terms of space.
Works directly with the integer representation, avoiding string overhead.
Cons
Still requires a loop, making it less efficient than a purely bitwise constant-time solution.
This is a highly efficient, constant-time solution that uses a clever bitwise trick. If a number n has alternating bits (e.g., 1010), then n XORed with n right-shifted by one (n >> 1) results in a number with all ones (e.g., 1010 ^ 0101 = 1111). A number made of all ones (like 1, 3, 7, 15, ...) has the property that when you add 1 to it, you get a power of two. We can check if a number y is a power of two by testing if (y & (y-1)) == 0.
Algorithm
- Create a new number
xby performing a bitwise XOR betweennandnright-shifted by one:x = n ^ (n >> 1). - If
nhas alternating bits,xwill be a number where all bits up to the most significant bit ofnare set to 1 (e.g.,...001111). - A number of the form
...001111is one less than a power of two. For example,7(0111) is one less than8(1000). - Therefore,
x + 1should be a power of two. - A positive number
yis a power of two if and only if(y & (y - 1)) == 0. - So, we check if
((x + 1) & x) == 0. If this condition is true, the bits are alternating; otherwise, they are not.
Walkthrough
This approach leverages properties of bitwise operations to solve the problem in constant time. The key insight is that for a number with alternating bits like n = 101010, the expression n ^ (n >> 1) will result in a number with all bits set to 1, like 111111. A number with all bits set to 1 is always one less than a power of two. We can check if a number k is a power of two by the property (k & (k - 1)) == 0. Combining these facts gives us a concise and fast solution.
class Solution { public boolean hasAlternatingBits(int n) { // n = 101010 // n >> 1 = 010101 // n ^(n>>1) = 111111 (let this be x) // x is of the form 2^k - 1. So x+1 is a power of 2. // A number is a power of 2 if (num & (num - 1)) == 0. // So, we check if ((x+1) & x) == 0. long x = n ^ (n >> 1); // Use long for x to handle the edge case where n has 31 bits // and x becomes 2^31 - 1. x+1 would overflow an int. return (x & (x + 1)) == 0; }}Complexity
Time
O(1). This approach consists of a fixed number of bitwise operations, regardless of the size of the input integer `n`.
Space
O(1). No extra space is used besides a single variable to store the intermediate result.
Trade-offs
Pros
Extremely efficient, providing a constant-time solution.
Demonstrates a deep understanding of bitwise operations.
Cons
The logic is less intuitive and harder to come up with compared to the iterative approaches.
Solutions
Solution
class Solution {public boolean hasAlternatingBits(int n) { n ^= (n >> 1); return (n & (n + 1)) == 0; }}class Solution {public: bool hasAlternatingBits(int n) { n ^= (n >> 1); return (n & ((long)n + 1)) == 0; }};class Solution: def hasAlternatingBits(self, n: int) -> bool: n ^= n >> 1 return (n & (n + 1)) == 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.