Binary Number with Alternating Bits
Easy · Bit Manipulation · Bit Manipulation
Problem
Given a positive integer n, return true if every two adjacent bits in its binary representation are different, so that the bits strictly alternate between 0 and 1. Otherwise return false.
The binary representation has no leading zeros: 5 is 101, not 0101.
Examples
Input: n = 21 Output: true
21 is 10101, which alternates all the way.
Input: n = 11 Output: false
11 is 1011, and its last two bits are both 1.
Input: n = 10 Output: true
10 is 1010; ending with 0 is fine.
Constraints
- 1 <= n <= 2^31 - 1
Approaches
- Compare each bit with the previous one — time O(log n), space O(1)
Follow-up
How many alternating numbers are there below 2^31? Exactly one per bit length (the leading bit is 1, so the rest is forced): 31 in all. The first use case counts them up to any n.
Related problems
Start free on Cariara · Coding problems · System design studio
