Last Updated: 18 Apr, 2021
NINJA'S COMPLEMENT
Easy
Asked in company
Everyday ninja sees a number in his dream but he doesn’t realize the meaning of that number. Somehow ninja manages to get the secret of his number. He comes to know that if he converts that number into binary and takes its complement and again converts it into decimal type he will get a lottery winning number of ‘Chit fund’ lottery.
But ninja is not good at maths so he is very sad about how he will get that lottery number from his dream’s number. So help our ninja in getting that lottery number.
Your task is to convert the given number into its binary form then take its complement ( Complement of a binary number is the value obtained by swapping all the bits i.e if ‘1’ is present you swap it with ‘0’ and vice versa ), then again convert it into its decimal representation.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains a single integer ‘N’ denoting the given number.
Output Format:
For each test case, return the number after doing its complement.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 10 ^ 6
Time Limit: 1 sec
Approaches
The idea here is to divide the number by ‘2’ as for converting a number from decimal to binary we need to divide it by ‘2’ while dividing we can think of taking complement as if we get remainder ‘1’ we can store it as ‘0’ and if we get ‘0’ we can store it as ‘1’.
Algorithm:
- Firstly we declare a variable ‘ANS’ which is used to store the final answer, ‘P’ is used to take the complement, and ‘K’ is used as a multiplier to convert binary number again into decimal where ‘ans’ is initialized with ‘0’ and ‘K’ with ‘1’
- Now we start iterating using a while loop which runs until our number is greater than ‘0’.
- In every iteration we check
- If the remainder is ‘0’ on dividing the number by ‘2’ we assign ‘P’ the value as ‘1’.
- Else we assign value to ‘P’ as ‘0’.
- Now we increase the ‘ANS += P * K'. In every iteration, we multiply the ‘K’ by ‘2’ and divided the ‘N’ by ‘2’.
- After the while loop, we return ‘ANS’.
The idea here is to use the concept that the xor of a number with its xor mask gives us the complement of the number. Xor mask of a number is greater than or equal to the number which has exactly the same number of bits as the given number and all bits of the xor mask is 1.
For example, 1 1 0 its xor mask is equal to 1 1 1 so we can think of as complement of a number is the value obtained by swapping ‘1’ with ‘0’ and vice versa so we can say when we take xor with its xor mask so according to xor when we encounter the same element it returns ‘0’ and if it is different it returns ‘1’.
So suppose given binary number is 1 1 0 its xor mask will be 1 1 1 on taking xor we get 0 0 1 and it is equal to complement.
Algorithm:
- Firstly, we check if our ‘N’ == 0 then we return ‘1’.
- Now we will declare a variable ‘TEMP’ and ‘TOTAL_BITS’ and initialize it with ‘N’ and ‘0’ respectively.
- Run a loop to count the total number of bits present in ‘N’. To do this we will run a loop until our ‘TEMP > 0’ and using the shift operator we decrease the value of ‘TEMP’ by ‘1’ bit and increase the count of ‘TOTAL_BITS’ by ‘1’ in each iteration.
- Now we simply store the xor mask by using 2 ^ TOTAL_BITS -1 and store it in the newly declared variable ‘XOR_MASK’.
- Now we can return ‘N ^ XOR_MASK’ as the final answer.