Last Updated: 7 Dec, 2020
X OR Y
Easy
Asked in companies
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.
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.
Approaches
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.