algoadvance

Leetcode 693. Binary Number with Alternating Bits

Problem Statement

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

Example 4:

Input: n = 10
Output: true
Explanation: The binary representation of 10 is: 1010

Clarifying Questions

  1. Range of n: What is the range of the input integer n?
    • The problem states that n is a positive integer, which typically means any positive integer within the range of a 32-bit integer.

Strategy

  1. Binary Representation and Bitwise Operations:
    • We will leverage bitwise operations to check for alternating bits.
    • Perform XOR of n with n >> 1. If n has alternating bits, the result will be all 1’s. For example, for n = 5 (binary 101), n >> 1 is 010, and 101 XOR 010 = 111.
    • Then add 1 to the result and check if it is a power of 2 (i.e., it has only one 1 bit in its binary representation). This condition ensures that the result is indeed all 1’s.
  2. Steps:
    1. Calculate n ^ (n >> 1).
    2. Add 1 to the result.
    3. Check if the result is a power of 2 by performing (result & (result - 1)) == 0.

Code

#include <iostream>

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

int main() {
    Solution solution;
    
    // Test cases
    int test_case_1 = 5;
    int test_case_2 = 7;
    int test_case_3 = 11;
    int test_case_4 = 10;

    std::cout << "Test Case 1 (5): " << solution.hasAlternatingBits(test_case_1) << std::endl; // Expected Output: true
    std::cout << "Test Case 2 (7): " << solution.hasAlternatingBits(test_case_2) << std::endl; // Expected Output: false
    std::cout << "Test Case 3 (11): " << solution.hasAlternatingBits(test_case_3) << std::endl; // Expected Output: false
    std::cout << "Test Case 4 (10): " << solution.hasAlternatingBits(test_case_4) << std::endl; // Expected Output: true

    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI