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:

Example 2:

Example 3:

Example 4:

Clarifying Questions

  1. Can the input integer be zero?
    • No, the input is a positive integer.
  2. Are there any constraints on the size of the integer?
    • The integer should be within the range of typical 32-bit signed integers.

Strategy

To determine if a number has alternating bits, we can follow these steps:

  1. Obtain the binary representation of the integer.
  2. Check adjacent bits to see if they are different.

A more efficient way involves avoiding the binary representation string manipulation:

  1. Perform bitwise operations to check alternating bits.
  2. Create a mask that, when XORed with the number, results in a number consisting entirely of 1s.

Code

public class Solution {
    public boolean hasAlternatingBits(int n) {
        // First, shift n right by one bit and XOR it with the original number
        int shifted = n >> 1;
        int xor = n ^ shifted;
        
        // Check if xor + 1 is a power of 2, which means xor must be of the form '111...111'
        return (xor & (xor + 1)) == 0;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.hasAlternatingBits(5)); // true
        System.out.println(sol.hasAlternatingBits(7)); // false
        System.out.println(sol.hasAlternatingBits(11)); // false
        System.out.println(sol.hasAlternatingBits(10)); // true
    }
}

Time Complexity

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