Last Updated: 8 Dec, 2020

No Adjacent Same

Easy

Asked in company

Solve now

Problem statement

You are given a 32-bit integer 'N'. At the right of the leftmost set bit, your task is to check if there are no two adjacent bits that are the same.

For Example :

42 is valid because it's binary representation '101010' has no two adjacent bits that are the same.

Input Format :

The first line contains a single integer T representing the number of test cases.

The first line of each test case will contain a single integer ‘N’ which denotes the given number.

Output Format :

For each test case, return true if no two adjacent bits are the same at the right of the leftmost set bit otherwise return false.

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Follow Up:

 Can you solve this using O(1) time complexity?

Constraints:

1 <= T <= 10
1 <= N <= 10^9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea is to first find the leftmost set bit and then check all the bits on the right of that, if the adjacent bits are the same or not.

Here is the algorithm:

Initialize a variable say ‘i’=31.
Run a loop from the leftmost bit i.e. 31 till 0:
- Initialize a variable ‘x’ = (1<<’i’) & n. This is done to check if ‘i-th’ bit of ‘n’ is set or not.
- If ‘x’ is not equal to zero, it means ‘i-th’ bit of ‘n’ is set (we found leftmost set bit):
  - Break.
Run a loop from ‘i’ till ‘1’:
- Initialize variable ‘x’ = (1<<’i’) & ‘n’. (to check if ‘i-th’ bit is set)
- Initialize variable ‘y’ = (1<<(‘i’-1)) & ‘n’. (to check if ‘i-1’th bit is set)
- If ‘x’ is not equal to zero and ‘y’ is not equal to zero (both adjacent bits are set):
  - Return ‘false’.
- Else If ‘x’ is equal to zero and ‘y’ is equal to zero (both adjacent bits are not set):
  - Return ‘false’.
Return ‘true’.

Solve now

02 Approach

The idea is to use XOR operator in such a way that if all the adjacent bits are different, then all the bits of the new number will be set to true, this is done so that the problem gets modified into: “check if all bits are set”.

Below is the algorithm:

Declare a new integer variable ‘num’.
Initialize ‘num’ = ‘N’ ^ (‘N’ >> 1), this is done to set all bits to true if adjacent bits are different.
Now, if ‘num’ & (‘num’ + 1) is equal to zero (that means all bits are set):
- Return ‘true’.
Else:
- Return ‘false’.

Solve now