Is Binary Number with Alternating Bits easy or hard?

LeetCode classifies this problem as Easy. The brute-force solution simply checks adjacent bits using shifting, while the optimized solution demonstrates a neat bitwise observation that reduces the check to constant time.

Binary Number with Alternating Bits Python/Java solution

In Python or Java, you can implement either the iterative bit-check loop using n & 1 and n >> 1, or the optimized XOR trick: int x = n ^ (n >> 1); return (x & (x + 1)) == 0;. Both implementations use constant extra space.

How to solve Binary Number with Alternating Bits in O(1)?

Use the property that alternating patterns become all 1s after XOR with a right-shifted version of the number. Compute x = n ^ (n >> 1) and then check whether x & (x + 1) equals 0. This confirms that the result is a continuous sequence of 1 bits, meaning the original number alternates.

What is the best approach for Binary Number with Alternating Bits?

The most efficient approach uses a bitwise trick: compute x = n ^ (n >> 1). If the original number had alternating bits, the XOR result becomes a sequence of all 1s. You can verify this by checking x & (x + 1) == 0. This runs in O(1) time and O(1) space.

Is Binary Number with Alternating Bits asked at Google/Amazon/Meta?

Bit manipulation questions similar to this appear frequently in interviews at companies like Google, Amazon, and Meta. The problem tests understanding of binary representation, shifting, XOR operations, and recognizing bit patterns efficiently.

What data structure is used in Binary Number with Alternating Bits?

No complex data structures are required. The solution relies purely on bit manipulation operations such as bitwise AND, XOR, and right shifts to inspect or transform the binary representation of the integer.

What is the time complexity of Binary Number with Alternating Bits?

The iterative bit-check approach runs in O(log n) time because it processes each bit of the number while repeatedly shifting right. The optimized XOR trick runs in O(1) time for fixed-width integers since it performs only a few bitwise operations.

Description Solution Video 18:09

693. Binary Number with Alternating Bits

Easy69.8% acceptance5 companies

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: 101

Example 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 <= 2³¹ - 1

Asked at 5 companies

Yahoo Amazon

Google Microsoft Bloomberg

Topics

Bit Manipulation

18:09

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

693. Binary Number with Alternating Bits

Asked at 5 companies

Topics

Similar problems