No Adjacent Same

Easy
0/40
Average time to solve is 10m
26 upvotes
Asked in company
Salesforce

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
21
31
Sample Output 1:
true
false
Explanation For Sample Input 1:
In example 1, binary representation of 21 is '10101'. Since, no two adjacent bits are the same here, it is valid.
In example 2, binary representation of 31 is ‘11111’. All the digits of binary representation are the same, hence it is not valid.
Sample Input 2:
2
20
85
Sample Output 2:
false
true
Explanation For Sample Input 2:
In example 1, binary representation of 20 is '10100'. Since, the 0-th and 1-st digits of the binary number are the same, it is invalid.
In example 2, binary representation of 85 is ‘1010101’. Since, no two adjacent bits are the same here, it is valid.
Hint

Can you iterate through each bit and check if adjacent bits are the same or different?

Approaches (2)
Iteration

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:
 

  1. Initialize a variable say ‘i’=31.
  2. 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.
  3. 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’.
  4. Return ‘true’.
Time Complexity

O(1),

 

Iterating through all the 32 bits of the integer takes O(32) time. Hence, the effective time complexity is O(1).

Space Complexity

O(1),

 

Since, no additional space is used to solve this problem, hence space complexity is O(1).

Code Solution
(100% EXP penalty)
No Adjacent Same
Full screen
Console