Given two numbers x and y, and a range [l, r] where 1 <= l, r <= 32. The task is consider set bits of y in range [l, r] and set these bits in x also.
Examples :
Input : x = 10, y = 13, l = 2, r = 3 Output : x = 14 Binary representation of 10 is 1010 and that of y is 1101. There is one set bit in y at 3'rd position (in given range). After we copy this bit to x, x becomes 1110 which is binary representation of 14. Input : x = 8, y = 7, l = 1, r = 2 Output : x = 11
Source : D E Shaw Interview
Method 1 (One by one copy bits)
We can one by one find set bits of y by traversing given range. For every set bit, we OR it to existing bit of x, so that the becomes set in x, if it was not set. Below is C++ implementation.
CPP
// C++ program to rearrange array in alternating// C++ program to copy set bits in a given// range [l, r] from y to x.#include <bits/stdc++.h>using namespace std;// Copy set bits in range [l, r] from y to x.// Note that x is passed by reference and modified// by this function.void copySetBits(unsigned &x, unsigned y, unsigned l, unsigned r){ // l and r must be between 1 to 32 // (assuming ints are stored using // 32 bits) if (l < 1 || r > 32) return ; // Traverse in given range for (int i=l; i<=r; i++) { // Find a mask (A number whose // only set bit is at i'th position) int mask = 1 << (i-1); // If i'th bit is set in y, set i'th // bit in x also. if (y & mask) x = x | mask; }}// Driver codeint main(){ unsigned x = 10, y = 13, l = 1, r = 32; copySetBits(x, y, l, r); cout << "Modified x is " << x; return 0;} |
Java
// Java program to rearrange array in alternating// Java program to copy set bits in a given// range [l, r] from y to x.import java.util.*;class GFG{// Copy set bits in range [l, r] from y to x.// Note that x is passed by reference and modified// by this function.static int copySetBits(int x, int y, int l, int r){ // l and r must be between 1 to 32 // (assuming ints are stored using // 32 bits) if (l < 1 || r > 32) return x; // Traverse in given range for (int i = l; i <= r; i++) { // Find a mask (A number whose // only set bit is at i'th position) int mask = 1 << (i-1); // If i'th bit is set in y, set i'th // bit in x also. if ((y & mask)!=0) x = x | mask; } return x;}// Driver codepublic static void main(String[] args){ int x = 10, y = 13, l = 1, r = 32; x = copySetBits(x, y, l, r); System.out.print("Modified x is " + x);}}// This code is contributed by umadevi9616 |
Python3
# Python program to rearrange array in alternating# Python program to copy set bits in a given# range [l, r] from y to x.# Copy set bits in range [l, r] from y to x.# Note that x is passed by reference and modified# by this function.def copySetBits(x, y, l, r): # l and r must be between 1 to 32 # (assuming ints are stored using # 32 bits) if (l < 1 or r > 32): return x; # Traverse in given range for i in range(l, r + 1): # Find a mask (A number whose # only set bit is at i'th position) mask = 1 << (i - 1); # If i'th bit is set in y, set i'th # bit in x also. if ((y & mask) != 0): x = x | mask; return x;# Driver codeif __name__ == '__main__': x = 10; y = 13; l = 1; r = 32; x = copySetBits(x, y, l, r); print("Modified x is ", x);# This code is contributed by gauravrajput1 |
C#
// C# program to rearrange array in alternating// C# program to copy set bits in a given// range [l, r] from y to x.using System;public class GFG { // Copy set bits in range [l, r] from y to x. // Note that x is passed by reference and modified // by this function. static int copySetBits(int x, int y, int l, int r) { // l and r must be between 1 to 32 // (assuming ints are stored using // 32 bits) if (l < 1 || r > 32) return x; // Traverse in given range for (int i = l; i <= r; i++) { // Find a mask (A number whose // only set bit is at i'th position) int mask = 1 << (i - 1); // If i'th bit is set in y, set i'th // bit in x also. if ((y & mask) != 0) x = x | mask; } return x; } // Driver code public static void Main(String[] args) { int x = 10, y = 13, l = 1, r = 32; x = copySetBits(x, y, l, r); Console.Write("Modified x is " + x); }}// This code is contributed by umadevi9616 |
Javascript
<script>// javascript program to rearrange array in alternating// javascript program to copy set bits in a given// range [l, r] from y to x. // Copy set bits in range [l, r] from y to x. // Note that x is passed by reference and modified // by this function. function copySetBits(x , y , l , r) { // l and r must be between 1 to 32 // (assuming ints are stored using // 32 bits) if (l < 1 || r > 32) return x; // Traverse in given range for (i = l; i <= r; i++) { // Find a mask (A number whose // only set bit is at i'th position) var mask = 1 << (i - 1); // If i'th bit is set in y, set i'th // bit in x also. if ((y & mask) != 0) x = x | mask; } return x; } // Driver code var x = 10, y = 13, l = 1, r = 32; x = copySetBits(x, y, l, r); document.write("Modified x is " + x);// This code is contributed by gauravrajput1</script> |
Output
Modified x is 15
Time Complexity: O(r)
Auxiliary Space: O(1)
Method 2 (Copy all bits using one bit mask)
CPP
// C++ program to copy set bits in a given// range [l, r] from y to x.#include <bits/stdc++.h>using namespace std;// Copy set bits in range [l, r] from y to x.// Note that x is passed by reference and modified// by this function.void copySetBits(unsigned &x, unsigned y, unsigned l, unsigned r){ // l and r must be between 1 to 32 if (l < 1 || r > 32) return ; // get the length of the mask int maskLength = (1ll<<(r-l+1)) - 1; // Shift the mask to the required position // "&" with y to get the set bits at between // l ad r in y int mask = ((maskLength)<<(l-1)) & y ; x = x | mask;}// Driver codeint main(){ unsigned x = 10, y = 13, l = 2, r = 3; copySetBits(x, y, l, r); cout << "Modified x is " << x; return 0;} |
Java
// Java program to copy set bits in a given// range [l, r] from y to x.import java.util.*;class GFG{// Copy set bits in range [l, r] from y to x.// Note that x is passed by reference and modified// by this function.static int copySetBits(int x, int y, int l, int r){ // l and r must be between 1 to 32 if (l < 1 || r > 32) return x; // get the length of the mask int maskLength = (int)((1L<<(r-l+1)) - 1); // Shift the mask to the required position // "&" with y to get the set bits at between // l ad r in y int mask = ((maskLength)<<(l-1)) & y ; x = x | mask; return x;}// Driver codepublic static void main(String[] args){ int x = 10, y = 13, l = 2, r = 3; x = copySetBits(x, y, l, r); System.out.print("Modified x is " + x);}}// This code is contributed by umadevi9616 |
Python3
# Python program to copy set bits in a given# range [l, r] from y to x.# Copy set bits in range [l, r] from y to x.# Note that x is passed by reference and modified# by this function.def copySetBits(x, y, l, r): # l and r must be between 1 to 32 if (l < 1 or r > 32): return x; # get the length of the mask maskLength = (int) ((1 << (r - l + 1)) - 1); # Shift the mask to the required position # "&" with y to get the set bits at between # l ad r in y mask = ((maskLength) << (l - 1)) & y; x = x | mask; return x;# Driver codeif __name__ == '__main__': x = 10; y = 13; l = 2; r = 3; x = copySetBits(x, y, l, r); print("Modified x is " , x);# This code is contributed by gauravrajput1 |
C#
// C# program to copy set bits in a given// range [l, r] from y to x.using System;public class GFG{ // Copy set bits in range [l, r] from y to x. // Note that x is passed by reference and modified // by this function. static int copySetBits(int x, int y, int l, int r) { // l and r must be between 1 to 32 if (l < 1 || r > 32) return x; // get the length of the mask int maskLength = (int) ((1L << (r - l + 1)) - 1); // Shift the mask to the required position // "&" with y to get the set bits at between // l ad r in y int mask = ((maskLength) << (l - 1)) & y; x = x | mask; return x; } // Driver code public static void Main(String[] args) { int x = 10, y = 13, l = 2, r = 3; x = copySetBits(x, y, l, r); Console.Write("Modified x is " + x); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// javascript program to copy set bits in a given// range [l, r] from y to x. // Copy set bits in range [l, r] from y to x. // Note that x is passed by reference and modified // by this function. function copySetBits(x , y , l , r) { // l and r must be between 1 to 32 if (l < 1 || r > 32) return x; // get the length of the mask var maskLength = parseInt( ((1 << (r - l + 1)) - 1)); // Shift the mask to the required position // "&" with y to get the set bits at between // l ad r in y var mask = ((maskLength) << (l - 1)) & y; x = x | mask; return x; } // Driver code var x = 10, y = 13, l = 2, r = 3; x = copySetBits(x, y, l, r); document.write("Modified x is " + x); // This code is contributed by gauravrajput1</script> |
Output
Modified x is 14
Time Complexity: O(1)
Auxiliary Space: O(1)
Thanks to Ashish Rathi for suggesting this solution in a comment.
This article is contributed by Rishi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
