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.
Solutions
Solution
class Solution {public boolean hasAlternatingBits(int n) { n ^= (n >> 1); return (n & (n + 1)) == 0; }}Video 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.