Binary Number with Alternating Bits

Tested Python solution for LeetCode 693 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 693, Easy. Topics: Bit Manipulation. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 693   # by problem number
lcpy gen -s binary_number_with_alternating_bits   # by problem name

​

Problem

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

​

Examples

Input: n = 5
Output: true
Explanation: The binary representation of 5 is: 101

Input: n = 7
Output: false
Explanation: The binary representation of 7 is: 111.

Input: n = 11
Output: false
Explanation: The binary representation of 11 is: 1011.

​

Constraints

• 1 <= n <= 2^31 - 1

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(1) (at most 31 iterations for the 32-bit constraint)
    # Space: O(1)
    def has_alternating_bits(self, n: int) -> bool:
        # x = n ^ (n >> 1) has every bit set iff adjacent bits all differ;
        # adding the carry back onto x must produce the next power of two.
        x = n ^ (n >> 1)
        return x & (x + 1) == 0

​

Complexity

Time	Space
O(1) (at most 31 iterations for the 32-bit constraint)	O(1)

​

Tags