X OR Y

Easy
0/40
Average time to solve is 15m
9 upvotes
Asked in companies
CitrixBYJUS

Problem statement

Given a number X. Find a positive number Y required to make binary representation of (X+Y) palindrome.


Also Y should be such that most significant set bit of (X+Y) should be same as the most significant set bit of X.

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 and only line of each test case contains a single integer ‘X’ denoting the given integer.
Output format: 
 Return the single integer denoting the possible value. The output for each test case is printed in a separate line. "YES" will be printed if (X+Y) is palindrome otherwise "NO".
Note: 
 You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1:
2    
6
10
Sample Output 1:
YES
YES
Explanation for Sample Output 1:
For the first test case :

1 is a possible number that will form a palindrome with 6.  6(110) + 1(001) = 7(111).

For the second test case :

5 is a possible number that will form a palindrome with 10. 5(0101) + 10(1010) = 15(1111)
Sample Input 2:
2
5
12
Sample Output 2:
YES
YES
Explanation for Sample Output 1:
For the first test case : 0
For the second test case : 3
Constraints:
1 <= ‘T’ <= 10
1 <= ‘X’ <= 10^18

Time Limit : 1 sec
Hint

Check the bits from 1st to N/2 from left and right of the binary representation of the number where N is the number of bits in the binary representation of the number ‘X’.

Approaches (1)
Bitmasking Approach

The main idea is to first convert the given number into its binary representation. the bits from 1st to N/2 from left and right of the binary representation of the number where N is the number of bits in the binary representation of the number. If they are equal then move to the next bit. If they are not equal we need to make them equal. If ith bit from left is 1 then add 2^(N-i-1) to the answer since we need to set the N-i-1 bit of the answer. Else add 2^(i) to the answer since we need to set ith bit from left in the answer. In this way, it will form a number with binary representation a palindrome and the given answer will be minimum.

 

Algorithm:-

  • Convert the given number ‘X’ to a string ‘temp’ such that it is the binary representation of the string.
  • Initialize the variable ans to  0
  • Run a loop from i equal to 0 to N/2 where N is the size of ‘temp’.
  • Check if the ith character and N - i - 1 are equal. If they are equal move to the next bit. Else check if the ith character is ‘0’ then add 2^(i) in the ans. Else add 2^(N - i - 1) in the ans.
  • Return the ans.
Time Complexity

 O(log2(X)) where ‘X’ is the given number.

 

 We are iterating over all the bits of X and the total number of bits in ‘X’ is log2(X) +1.

Space Complexity

O(log2(X)) where ‘X’ is the given number.

 

We are converting the given number to a string which is a binary representation of ‘X’.The size of the string is log2(X)+1  where log2(X) + 1 is the total number of bits in ‘X’.

Code Solution
(100% EXP penalty)
X OR Y
Full screen
Console