693. Binary Number with Alternating Bits

EasyBit Manipulation

Problem Description

In this problem, we are given a positive integer, and our task is to determine whether this number represents a binary sequence of alternating bits. In other words, we have to check if every pair of adjacent bits in the binary representation of the positive integer is different. For instance, the integer 5, which in binary is 101, has alternating bits, whereas the integer 7, which in binary is 111, does not.

Intuition

To solve this problem, the solution utilizes bitwise operations, which are perfect for manipulating binary numbers directly. Here is the intuition broken down into steps:

We perform an XOR operation on the number n with itself shifted one bit to the right, n >> 1. An XOR operation will give us a 1 only when the two bits being compared are different. With the shifting, every pair of adjacent bits will be compared. If n has alternating bits, then this operation should result in a binary number composed entirely of 1s.
Now we need to verify that after the XOR operation, the number indeed consists of all 1s. For a binary number composed entirely of 1s (let's call it m), adding one to it, m + 1, will result in a binary number with a 1 followed by 0s (because it carries over). For example, if m is 111 in binary, m + 1 would be 1000.
If we perform a binary AND operation between m and m + 1, it should give us 0 because there are no common 1 bits between, for example, 111 (m) and 1000 (m + 1). The code checks this with (n & (n + 1)) == 0.

Putting all this together, if the number after the XOR and shift has alternating bits, it will be a string of 1s, and applying the described AND operation will yield 0, confirming that our number n had alternating bits.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Depth First SearchBreadth First Search

I don’t know

Solution Approach

The given solution's implementation uses bitwise operations, which is a common and efficient way to solve problems that involve bit manipulation due to their low-level nature and high speed of execution.

Let's walk through the code:

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

The statement n ^= n >> 1 uses the XOR (^=) operation and the right shift operator (>>). The right shift operator moves each bit of n to the right by one position. The XOR operation then compares the original n with its shifted version; if n had alternating bits, this operation will yield a number with all 1s because the different adjacent bits (when compared with XOR) return 1.
After the XOR operation, the solution checks if the resulting number has all 1s. To do this, it adds 1 to the number (n + 1) and then does a bitwise AND (&) with the original number (n). If the resulting number is 0, that confirms that all the bits in n were 1, due to the fact that a binary number with all 1s plus 1 will result in a power of two, which in binary is represented as 1000...0 (a one followed by zeroes).
The expression (n & (n + 1)) == 0 does the final check. If it evaluates to True, then the number n originally passed in had alternating bits. If not, the bits did not alternate.

This approach cleverly leverages the characteristics of binary arithmetic to solve the problem with just two operations, highlighting the efficiency and elegance of bitwise manipulation.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Example Walkthrough

Let's use the number 10 as a small example to illustrate the solution approach. The binary representation of 10 is 1010.

Step 1: Perform an XOR between n and n >> 1

Original n in binary: 1010
n >> 1 (shifted to right by one): 0101
XOR operation: n ^ (n >> 1) = 1010 ^ 0101 = 1111

After the XOR operation, the number n becomes 1111, which is composed entirely of 1s. This outcome is expected for a number with alternating bits.

Step 2: Add 1 to n and perform a bitwise AND between n and n + 1

n: 1111
n + 1: 10000
AND operation: n & (n + 1) = 1111 & 10000 = 0

Step 3: Conclusion

Since n & (n + 1) equals 0, we can conclude that the original number 10 does indeed have alternating bits. The bitwise operations have confirmed that every adjacent pair of bits in the binary representation of 10 was different. The solution works as intended for the example of 10.

In the case of a number without alternating bits, these two steps would lead to a non-zero result when performing the AND operation. Therefore, the condition would not be met, and the method would correctly indicate that the number does not have alternating bits.

Solution Implementation

1class Solution:
2    def has_alternating_bits(self, number: int) -> bool:
3        # XOR the number with itself right-shifted by one bit.
4        # This combines each pair of bits (starting from the least significant bit)
5        # and turns them into 1 if they were different (10 or 01), and 0 if they were the same (00 or 11).
6        number ^= number >> 1
7
8        # After the XOR operation, a number that had alternating bits like ...010101
9        # becomes ...111111. To check if this is the case, we can add 1 to the number
10        # resulting in ...1000000 (if the number was truly all 1s).
11      
12        # Then we do an 'AND' operation with its original value. If the number had 
13        # all 1s after the XOR, this operation will result in 0 because of no overlapping bits.
14        # For example, for a number with alternating bits:
15        #   After XOR:  011111 (31 in decimal, for number 21 which is 10101 in binary)
16        #   Number + 1: 100000 (32 in decimal)
17        #   AND op:     000000 (0 in binary)
18        # If the resulting number is 0, then the input number had alternating bits.
19        return (number & (number + 1)) == 0
20

1class Solution {
2
3    public boolean hasAlternatingBits(int number) {
4        // XOR the number with itself shifted right by 1 bit.
5        // This will convert the number into a binary representation of all 1's
6        // if it has alternating bits (e.g., 5 in binary is 101, and 5 ^ (5 >> 1) = 7, which is 111 in binary).
7        number ^= (number >> 1);
8
9        // Check if the number after XOR (now in the form of all 1's if bits are alternating)
10        // AND the number incremented by 1 is zero.
11        // Incrementing will shift all 1's to a leading 1 followed by all 0's (e.g., 111 becomes 1000).
12        // If the bits in the number were alternating, then (number & (number + 1)) must be 0.
13        return (number & (number + 1)) == 0;
14    }
15}
16

1class Solution {
2public:
3    bool hasAlternatingBits(int n) {
4        // Perform XOR between number and its one bit right shift.
5        // This will convert a sequence like '1010' into '1111' if the bits alternate,
6        // or into some other pattern that is not all 1's if they don't.
7        n ^= (n >> 1);
8      
9        // Add 1 to the transformed number to set the rightmost 0 bit to 1 (if any).
10        // This will result in a number with all bits set to 1 only if n was already all 1's.
11        long nPlusOne = static_cast<long>(n) + 1;
12      
13        // Perform bitwise AND between n and nPlusOne.
14        // If n had all bits set to 1 before, then n & nPlusOne will be zero,
15        // indicating that the original number had alternating bits.
16        // If n had any 0s, this operation will produce a non-zero result.
17        return (n & nPlusOne) == 0;
18    }
19};
20

1function hasAlternatingBits(n: number): boolean {
2    // Perform XOR between the number n and its one bit right-shifted self.
3    // This operation will convert a sequence like '1010' into '1111' if the bits alternate,
4    // or into some other pattern that contains '0's if they don't alternate.
5    n ^= (n >> 1);
6  
7    // Cast n to a number representation that can safely hold a larger value (using bitwise OR with 0).
8    // Then add 1 to the transformed number (from above) to set the least significant 0 bit to 1 (if any exist).
9    // This will result in a number with all bits set to 1 only if n was already composed exclusively of 1's.
10    let nPlusOne: number = (n | 0) + 1;
11  
12    // Perform a bitwise AND between n and nPlusOne.
13    // If n was composed exclusively of 1's before adding one, then n & nPlusOne will be zero,
14    // indicating that the original number indeed had alternating bits.
15    // If n contained any 0's before adding one, this operation will produce a non-zero result.
16    return (n & nPlusOne) === 0;
17}
18

Not Sure What to Study? Take the 2-min Quiz：

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Time and Space Complexity

The given code is a method to check whether a number has alternating bits or not. Let's analyze the time and space complexity:

Time Complexity

The code performs the following operations:

n ^= n >> 1: This is a bitwise XOR operation applied to the number and its right-shifted version by one bit. It runs in O(1) time since the operation is performed on a fixed number of bits that constitutes the number n.
(n & (n + 1)) == 0: This operation checks if the result from the first operation+1 is a power of two which guarantees alternating bits (since it would set all bits to zero). This also runs in O(1) time for the same reason as the bitwise XOR operation.

Since both operations are constant time operations, the overall time complexity of the function is O(1).

Space Complexity

The space complexity refers to the amount of extra memory used aside from the input. In this case, the function uses a fixed amount of memory to store the results of the operations, regardless of the size of n.

There are no additional data structures used that grow with the size of the input. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

693. Binary Number with Alternating Bits

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings