693. Binary Number with Alternating Bits Solution

The problem

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

Approach overview

Problem Overview: Given a positive integer n, determine whether its binary representation contains alternating bits. That means every adjacent bit must differ, such as 101010 or 10. If any two neighboring bits are the same (like 110 or 1001), the number does not satisfy the condition.

Approach 1: Observation and Iterative Check (Time: O(log n), Space: O(1))

The straightforward solution inspects bits one by one from right to left. Extract the last bit using n & 1, then shift the number right using n >> 1. Track the previous bit and compare it with the current bit during each iteration. If two consecutive bits match, the pattern breaks and you return false.

This works because each right shift removes the least significant bit, letting you compare neighbors sequentially. The loop runs once for every bit in the number, which is O(log n) since the number of bits grows logarithmically with the value of n. Space remains O(1) because only a few variables are used.

This approach is easy to reason about and shows clear understanding of bit manipulation. It is often the first solution candidates write during interviews.

Approach 2: Bitwise Comparison Trick (Time: O(1), Space: O(1))

A more elegant approach relies on a useful property of alternating bit patterns. If you XOR a number with itself shifted right by one (x = n ^ (n >> 1)), the result becomes a sequence of all 1 bits when the original number had perfectly alternating bits. For example, 1010 ^ 0101 = 1111.

Once you obtain x, check whether it consists only of consecutive 1s. A number with all 1s has the property x & (x + 1) == 0. This works because adding 1 flips the entire run of 1s and introduces a carry into a new bit. If the AND operation returns zero, the pattern is valid.

This method compresses the entire validation into a couple of bit manipulation operations and avoids looping through individual bits. Runtime is effectively O(1) for fixed-width integers, with O(1) space.

Recommended for interviews: Start with the iterative bit check because it clearly demonstrates understanding of binary representation and shifting. After that, mention the XOR trick as an optimization. Interviewers typically expect the n ^ (n >> 1) insight since it shows strong familiarity with bit patterns and low-level operations.

Approach 1: Bitwise Comparison Approach

In this approach, we will use bitwise operations to compare each bit with its adjacent one. The key is to repeatedly XOR the number with itself shifted one position to the right, which will result in a number with all bits set to 1 if the original number has alternating bits. Such a number should satisfy (n & (n + 1)) == 0.

Python

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        xor = n ^ (n >> 1)
        return (xor & (xor + 1)) == 0

Java

public class Solution {
    public boolean hasAlternatingBits(int n) {
        int xor = n ^ (n >> 1);
        return (xor & (xor + 1)) == 0;
    }
}

C++

#include <iostream>

bool hasAlternatingBits(int n) {
    int xor_result = n ^ (n >> 1);
    return (xor_result & (xor_result + 1)) == 0;
}

JavaScript

function hasAlternatingBits(n) {
    let xor = n ^ (n >> 1);
    return (xor & (xor + 1)) === 0;
}

#include <stdbool.h>

bool hasAlternatingBits(int n) {
    int xor = n ^ (n >> 1);
    return (xor & (xor + 1)) == 0;
}

public class Solution {
    public bool HasAlternatingBits(int n) {
        int xor = n ^ (n >> 1);
        return (xor & (xor + 1)) == 0;
    }
}

The solution leverages Python's bitwise operations to determine if a number’s binary representation has alternating bits by exploiting the XOR between the number and its shifted version.

Complexity

Time Complexity: O(1), Space Complexity: O(1)

Try this approach in the editor

Approach 2: Observation and Iterative Check

This approach involves checking each bit pair iteratively. We will repeatedly check if the last two bits are the same or different by analyzing the least significant bits and shifting the number to the right iteratively.

Python

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        while n > 0:
            last = n % 2
            n = n >> 1
            if last == (n % 2): return False
        return True

Java

public class Solution {
    public boolean hasAlternatingBits(int n) {
        while (n > 0) {
            int last = n % 2;
            n = n >> 1;
            if (last == (n % 2)) return false;
        }
        return true;
    }
}

C++

#include <iostream>

bool hasAlternatingBits(int n) {
    while(n > 0) {
        int last = n % 2;
        n = n >> 1;
        if(last == (n % 2)) return false;
    }
    return true;
}

JavaScript

function hasAlternatingBits(n) {
    while(n > 0) {
        let last = n % 2;
        n = n >> 1;
        if (last === (n % 2)) return false;
    }
    return true;
}

#include <stdbool.h>

bool hasAlternatingBits(int n) {
    while(n > 0) {
        int last = n % 2;
        n = n >> 1;
        if (last == (n % 2)) return false;
    }
    return true;
}

public class Solution {
    public bool HasAlternatingBits(int n) {
        while (n > 0) {
            int last = n % 2;
            n = n >> 1;
            if (last == (n % 2)) return false;
        }
        return true;
    }
}

The Python solution checks bits iteratively, each time reducing the number by shifting right and comparing the least significant bit.

Complexity

Time Complexity: O(log N), where N is the integer value. Space Complexity: O(1)

Try this approach in the editor

Approach 3: Simulation

We cyclically right-shift n until it becomes 0, checking whether the binary bits of n appear alternately. If during the loop we find that 0 and 1 do not appear alternately, we directly return false. Otherwise, when the loop ends, we return true.

The time complexity is O(log n), and the space complexity is O(1).

TypeScript

function hasAlternatingBits(n: number): boolean {
    let prev = -1;

    while (n !== 0) {
        const curr = n & 1;
        if (prev === curr) {
            return false;
        }
        prev = curr;
        n >>= 1;
    }

    return true;
}

func hasAlternatingBits(n int) bool {
	prev := -1
	for n != 0 {
		curr := n & 1
		if prev == curr {
			return false
		}
		prev = curr
		n >>= 1
	}
	return true
}

Rust

impl Solution {
    pub fn has_alternating_bits(mut n: i32) -> bool {
        let mut prev: i32 = -1;

        while n != 0 {
            let curr = n & 1;
            if prev == curr {
                return false;
            }
            prev = curr;
            n >>= 1;
        }

        true
    }
}

Try this approach in the editor

Approach 4: Bit Manipulation

Assuming 01 appears alternately, we can convert all trailing bits to 1 through misaligned XOR. Adding 1 gives us a power of 2, which is a number n (where n has only one bit that is 1). Then, using n \& (n + 1) can eliminate the last 1 bit.

At this point, check if it equals 0. If so, the assumption holds, and it is an alternating 01 sequence.

The time complexity is O(1), and the space complexity is O(1).

TypeScript

function hasAlternatingBits(n: number): boolean {
    n ^= n >> 1;
    return (n & (n + 1)) === 0;
}

func hasAlternatingBits(n int) bool {
	n ^= (n >> 1)
	return (n & (n + 1)) == 0
}

Rust

impl Solution {
    pub fn has_alternating_bits(n: i32) -> bool {
        let mut x = n ^ (n >> 1);
        (x & (x + 1)) == 0
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Bitwise Comparison Approach	Time Complexity: O(1), Space Complexity: O(1)
Observation and Iterative Check	Time Complexity: O(log N), where N is the integer value. Space Complexity: O(1)
Simulation	–
Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Observation and Iterative Bit Check	O(log n)	O(1)	Best when explaining logic step‑by‑step in interviews or when demonstrating understanding of binary traversal.
Bitwise XOR Comparison Trick	O(1)	O(1)	Preferred optimized solution using bit manipulation properties and constant-time checks.

Frequently asked questions

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.

Binary Number with Alternating Bits solution and explanation

The problem

Approach overview

Approach 1: Bitwise Comparison Approach

Approach 2: Observation and Iterative Check

Approach 3: Simulation

Approach 4: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Binary Number with Alternating Bits solution and explanation

The problem

Approach overview

Approach 1: Bitwise Comparison Approach

Approach 2: Observation and Iterative Check

Approach 3: Simulation

Approach 4: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems