Toggle K bits

Easy
0/40
Average time to solve is 10m
42 upvotes
Asked in company
Codenation

Problem statement

You are given a 32-bit integer ‘N’. Your task is to toggle the rightmost ‘K’ bits in the given integer and return the new integer.

For Example : 
If ‘N’ = 12 and ‘K’ = 2:
The binary representation of 12 is ‘1100’, after toggling rightmost 2 bits, it becomes ‘1111’ i.e. 15. Hence, the answer is 15.
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 two space-separated integers ‘N’ and ‘K’ that represent the given 32-bit integer and number of rightmost bits to toggle respectively.
Output format : 
For each test case, return the new Integer after toggling the rightmost ‘K’ bits.
Note: 
You don’t need to print anything, it has already been taken care of. Just implement the given function
Follow Up: 
 Can you solve this using O(1) time complexity?
Constraints: 
1 <= T <= 10
1 <= N <= 10^9
1 <= K <= 31

Time Limit: 1 sec
Sample Input 1:
2
21 3
40 4
Sample Output 1:
18
39
Explanation For Sample Input 1:
In example 1, the binary representation of 21 is '10101'. After toggling rightmost 3 bits, it becomes ‘10010’ which is equal to 18.
In example 2, the binary representation of 40 is ‘101000’. After toggling rightmost 4 bits, it becomes ‘100111’ which is equal to 39.
Sample Input 2:
2 
20 2
85 5
Sample Output 2:
23
74
Explanation For Sample Input 2:
In example 1, the binary representation of 20 is '10100'. After toggling rightmost 2 bits, it becomes ‘10111’ which is equal to 23.
In example 2, the binary representation of 85 is ‘1010101’. After toggling rightmost 5 bits, it becomes ‘1001010’ which is equal to 74.
Hint

Can you toggle all the rightmost ‘K’ bits one by one?

Approaches (2)
Iteration And Bit Manipulation

The idea is to simply iterate through the rightmost ‘K’ bits and toggle them one by one using the XOR operator.

 

Here is the algorithm:
 

  1. Run a loop from 0 to ‘K’-1 (say iterator ‘i’):
    • Update ‘N’ = ‘N’ xor (1 << (‘i’)). This is done to toggle the ‘i-th’ bit.
  2. Return ‘N’.
Time Complexity

O(1),

 

Iterating through all the ‘K’ bits of the integer takes O(K) time. Since ‘K’ is less than or equal to 31, the effective time complexity is O(1).

Space Complexity

O(1), 

 

Since, no additional space is used to solve this problem, hence space complexity is O(1).

Code Solution
(100% EXP penalty)
Toggle K bits
Full screen
Console