02. Copy Set Bits in Range

The problem can be found at the following link: Question Link

My approach

This is a simple bit masking question where we need to generate a mask to filter out specific bits from y and then perform a bitwise OR operation (x or y) to copy the values of y into x.

To create the mask, follow these steps:

• First, determine the length of the filter mask.

• Create the mask by left-shifting 1 by the mask length.

• Obtain the desired mask by subtracting 1 from the mask and left-shifting it by l - 1.

• Once the mask is ready, apply it to filter out the relevant bits from y, and perform a bitwise OR operation with x to copy the filtered values into x.

Example

Given:
- x = 1090 (10001000010)
- y = 1211 (10010111011)
- l = 2
- r = 6

Steps:

1. Since l = 2 and r = 6 are inclusive in the range, 
   maskLen = 5.

2. Calculate the mask:
   - Initialize mask as 1 shifted left by maskLen: mask = 1 << 5 = 32 (100000)

   - Subtract 1 from mask: mask = mask - 1 = 31 (011111)
     (We obtain a mask with the required length of 5 ones)

   - Shift the mask towards the left boundary by (l - 1): mask = mask << (l - 1) = (0111110)
     (This is our required mask)
 
 3. Filter out y value:
    y' = y & mask = (10010111011) & (0111110) = (0111010)

 4. Copy x or y:
    Result = x | y' = (10001000010) | (0111010) = 1146 (10001111010)

Time and Auxiliary Space Complexity

• Time Complexity : O(1), as it does not depend on the size of the inputs x and y.

• Auxiliary Space Complexity : constant as it does not depend on variables

Code (C++)

class Solution {
public:
    int setSetBit(int x, int y, int l, int r) {
        int maskLen = r - l + 1;
        int mask = (1 << maskLen) - 1;
        mask = mask << (l - 1);
        y = y & mask;
        return (x | y);  
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.