Flip given bits

Easy
0/40
Average time to solve is 15m
19 upvotes
Asked in companies
QualcommIBM

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
21
3
4 2 1
40
1
4
Sample Output 1:
30
32
Explanation for Sample Input 1:
Before flipping
21 => 10101
After flipping the 4th, 2nd and 1st bit from the end we get 
30 => 11110

Before flipping
40 => 101000
After flipping the 4th bit from the end we get 
32 => 100000
Sample Input 2:
1
5
3
6 2 5
Sample Output 2:
55
Hint

Try to use the bitwise operators to perform the bit flipping.

Approaches (2)
Bitwise Flipping of Bits

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’.
Time Complexity

O(N), where ‘N’ is the length of the given array ‘ARR’.

 

Since we are iterating over all the indices of the array ‘ARR’ and flipping respective bits hence, the complexity here grows by O(N).

Space Complexity

O(1).

 

Since constant space is being used here, therefore, the space complexity is O(1).

Code Solution
(100% EXP penalty)
Flip given bits
Full screen
Console