Copy Bits in Range

Moderate
0/80
9 upvotes
Asked in companies
AdobeD.E.Shaw

Problem statement

Ninja is learning the binary representation and bit manipulation. He found an interesting question but had no hints on how to solve it. The question statement says two numbers, ‘A’ and ‘B’ are given, and a range ‘X’ to ‘Y’ is given. You have to copy the set bits of ‘A’ in the range ‘X’ to ‘Y’ in ‘B’ and print the modified value of ‘B’.Can you help Ninja in solving this problem?

For Example 
If ‘A’ is 13(1101) and ‘B’ is 7(0111), and the range is 2 to 4. So, we will copy the set bits in the range 2 to 4 from the left. The set bits in this range are the 3rd bit and the 4th bit. So, we will copy these bits to ‘B’.Now, the modified B will be 15(1111) as we copied the 4th bit.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains four integers, ‘A’ and ‘B’, and the range ‘X’ and ‘Y.’
Output Format: 
For each test case, print ‘an integer corresponding to the modified value of ‘B’.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= ‘A’,’B’ <= 10^9.
1 <= ‘X’,’Y’ <= 30.

Time limit: 1 sec
Sample Input 1:
2
13 7 2 4
10 18 2 3
Sample Output 1:
15
18
Explanation of sample input 1:
For the first test case,

The binary representation of 13 is 1101.
The binary representation of 7 is 0111.
So, the set bits of ‘A’ in the given range are the 3rd bit and the 4th bit.
So, we will copy these set bits in ‘B’.B will become 15(1111).
Hence, the answer is 15.


For the second test case:

The binary representation of 10 is 01010.
The binary representation of 18 is 10010.
So, the set bits of ‘A’ in the given range is the 2nd bit only.
So, we will copy these set bits in ‘B’.B will become 18(10010).
Hence, the answer is 18.
Sample Input 2:
2
6 19 1 3
3 2 2 4
Sample Output 2:
23
2
Hint

Find the all set bits of ‘A’ in the given range.

Approaches (2)
Brute Force.

In this approach, we will simply iterate in the range ‘X’ to  ‘Y’ and find if the bit is set in ‘A’ or not. If the bit is set, we will copy the corresponding bit in ‘B,’ and at last, we will return the modified B.

 

Algorithm:

  • For i in range X to Y, do the following:
    • If ( A & 1<<(i-1)) is greater than 0:
      • It implies the ith bit is set in ‘A’.
      • Modify ‘B’ as ‘B’ | (1<<(i-1)).
  • Return ‘B’.
Time Complexity

O(R), where ‘R’ is the length of the range.

 

In this approach, we are checking in the range X to Y whether the bit is set or not and copying it in ‘B’ using bitwise operations, which takes O(1) time. Hence, the overall time complexity is O(R).

Space Complexity

O(1).
 

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Copy Bits in Range
Full screen
Console