693. Binary Number with Alternating Bits

2020, Nov 25 2 mins read

1. Description

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

2. Example

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.

Example 5

Input: n = 3
Output: false

3. Constraints

1 <= n <= 2$^{31}$ - 1

4. Solutions

Bit Manipulation

Time complexity: O(1)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution
{
public:
    // bool hasAlternatingBits(int n)
    bool hasAlternatingBits(int num)
    {
        // pass leading zero
        int leftMove = 31;
        while((num & (1 << leftMove)) == 0) leftMove--;

        int lastOnePosition = INT_MAX, lastZeroPosition = INT_MAX;
        for(; leftMove >= 0; leftMove--)
        {
            if(num & (1 << leftMove))
            {
                if(lastOnePosition - leftMove == 1) return false;

                lastOnePosition = leftMove;
            }
            else
            {
                if(lastZeroPosition - leftMove == 1) return false;

                lastZeroPosition = leftMove;
            }
        }

        return true;
    }
};

Search

Tags