Skip to main content

Binary Number with Alternating Bits

Problem Description​

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

Examples​

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.

Constraints​

  • 1≤n≤231−11 \leq n \leq 2^{31} - 1

Solution for Binary Number with Alternating Bits​

Approach 1: Convert to String​

Intuition and Algorithm​

Let's convert the given number into a string of binary digits. Then, we should simply check that no two adjacent digits are the same.

Code in Different Languages​

Written by @Shreyash3087
class Solution {
public boolean hasAlternatingBits(int n) {
String bits = Integer.toBinaryString(n);
for (int i = 0; i < bits.length() - 1; i++) {
if (bits.charAt(i) == bits.charAt(i+1)) {
return false;
}
}
return true;
}
}

Complexity Analysis​

Time Complexity: O(1)O(1)​

Reason: For arbitrary inputs, we do O(w)O(w) work, where w is the number of bits in n. However, w≤32w \leq 32.

Space Complexity: O(1)O(1)​

Reason: or alternatively O(w)O(w).

Approach 2: Divide By Two​

Algorithm​

We can get the last bit and the rest of the bits via n % 2 and n // 2 operations. Let's remember cur, the last bit of n. If the last bit ever equals the last bit of the remaining, then two adjacent bits have the same value, and the answer is False. Otherwise, the answer is True.

Also note that instead of n % 2 and n // 2, we could have used operators n & 1 and n >>= 1 instead.

Code in Different Languages​

Written by @Shreyash3087
class Solution {
public boolean hasAlternatingBits(int n) {
int cur = n % 2;
n /= 2;
while (n > 0) {
if (cur == n % 2) return false;
cur = n % 2;
n /= 2;
}
return true;
}
}

Complexity Analysis​

Time Complexity: O(1)O(1)​

Reason: For arbitrary inputs, we do O(w)O(w) work, where w is the number of bits in n. However, w≤32w \leq 32.

Space Complexity: O(1)O(1)​

Reason: constant space is used.

References​


Authors:

Loading...