Last Updated: 8 Dec, 2020
Flip given bits
Easy
Asked in companies
You have been given an integer 'NUM' (32 bits) and an array of size 'N'.
Your task is to flip all the bits of 'NUM' at position 'ARR[i]' where 0<= i <= N-1.
Input format :
The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains an integer 'NUM' representing the number whose binary representation is to be flipped.
The second line of each test case contains an integer 'N' representing the size of the array/list.
The third line of each test case contains 'N' single space-separated integers representing the elements of the given array/list ‘ARR’.
Output format :
For each test case, print a single line containing an integer that represents the Modified Integer.
Output for each test case will be printed in a separate line.
Note
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints:
1 <= 'T' <= 10
1 <= 'NUM' <= 10^9
1 <= 'N' <= 10^5
1 <= 'ARR[i]' <= 31
Time Limit: 1 sec
Approaches
The problem could be solved by first using the left shift operator on the binary representation of the number 1 upto every index given ‘ARRAY[i]’ so that the bit ‘1’ is shifted to the required index of the bit which is to be flipped. Now perform bitwise XOR between the shifted result and the given number ‘NUM’ and update ‘NUM’ with the new result.
The steps are as follows :-
- Start iterating on the given array of indices ‘ARRAY’ of bits to be shifted in the number ‘NUM’.
- Now, for every index ‘ARRAY[i]’ keep performing a left bitwise shift operation on the number 1.
- Now perform bitwise XOR between the number ‘NUM’ and the above obtained result and also update the value of the number ‘NUM’ with the result obtained after all these operations.
- Finally, return the result which is stored in our given number whose bits were required to be flipped ‘NUM’.
A potential solution to this problem could be to use the library (api) present in the respective programming language (like bitset in C++) and (the ‘bin’ and ‘int’ function in python) to convert a decimal number given M (integer) into its respective binary representation (string or character array) which can then be used to flip the bits at all the given indices as per the indices array ('ARR[i]') starting from the end of the binary representation.
The steps are as follows :-
- Initialise a string/character array for storing the 32 bit representation ‘BIN’ of the given integer (decimal number) ‘NUM’ and the size of the binary representation as ‘BIN_SIZE’. (which would be 32).
- Now, after converting the number into its respective 32-bit binary representation we traverse the given array ‘ARR’ of indices of the bits in the binary number.
- If the bit at the index (‘BIN_SIZE’ - ‘ARR[i]’) is ‘0’ then it is flipped to ‘1’ otherwise if the bit is ‘1’ it is flipped to ‘0’.
- Finally, convert the obtained string/character array representation back to integer (decimal) and return the result.