Given three integers L, R, and K, the task is to find the minimum Bitwise XOR of at most K integers between [L, R].
Examples:
Input: L = 1, R = 10, K = 3
Output: 0
Explanation:
Choose elements 4, 5, and 1 in the range [1, 10] and the Bitwise XOR of the chosen elements is 0, which is minimum.Input: L = 32, R = 33, K = 2
Output: 1
Explanation:
Choose elements 32, and 33 in the range [32, 33] and the Bitwise XOR of the chosen elements is 1, which is minimum.
Brute Force Approach:
- Initialize min_xor to INT_MAX, which represents the largest possible integer value in C++.
- Iterate over all possible values of k from 1 to K.
- For each value of k, initialize a vector to store the current combination of k integers, and initialize the first k elements of the combination to L, L+1, …, L+k-1.
- Generate all possible combinations of k integers between L and R using a modified version of the algorithm to generate combinations, where we increment the rightmost element of the combination if possible and adjust the remaining elements accordingly.
- For each combination, calculate the XOR value of the current combination by iterating over all elements of the combination and performing the XOR operation. Store the minimum XOR value encountered so far in min_xor.
- Return the final value of min_xor as the minimum bitwise XOR of at most K integers between [L, R].
C++
//code to implement brute force approach for this problem#include <bits/stdc++.h>using namespace std;int min_bitwise_xor(int L, int R, int K){ int min_xor = INT_MAX; // Iterate over all possible values of k from 1 to K for (int k = 1; k <= K; k++) { // Initialize a vector to store the current // combination vector<int> comb(k); // Initialize the first k elements of the // combination to L, L+1, ..., L+k-1 for (int i = 0; i < k; i++) { comb[i] = L + i; } // Generate all possible combinations of k integers // between L and R while (comb[k - 1] <= R) { // Calculate the XOR value of the current // combination int xor_val = 0; for (int num : comb) { xor_val ^= num; } // Update the minimum XOR value if necessary min_xor = min(min_xor, xor_val); // Check if we have reached the end of the range // [L, R] if (comb[k - 1] == R) { break; } // Find the rightmost index j such that comb[j] // can be incremented int j = k - 1; while (j >= 0 && comb[j] == R - k + j + 1) { j--; } // If j is negative, we have generated all // possible combinations if (j < 0) { break; } // Increment comb[j] and adjust the remaining // elements of the combination comb[j]++; for (int i = j + 1; i < k; i++) { comb[i] = comb[i - 1] + 1; } } } // Return the minimum XOR value return min_xor;}int main(){ int L = 1, R = 10, K = 3; // Find the minimum bitwise XOR of at most K integers // between [L, R] int min_xor = min_bitwise_xor(L, R, K); // Print the result cout << min_xor << endl; return 0;} |
Python3
# code to implement brute force approach for this problemimport sysdef min_bitwise_xor(L, R, K): min_xor = sys.maxsize # Iterate over all possible values of k from 1 to K for k in range(1, K+1): # Initialize a array to store the current # combination comb = [i for i in range(L, L+k)] # Generate all possible combinations of k integers # between L and R while comb[k-1] <= R: # Calculate the XOR value of the current # combination xor_val = 0 for num in comb: xor_val ^= num # Update the minimum XOR value if necessary min_xor = min(min_xor, xor_val) if comb[k-1] == R: break # Find the rightmost index j such that comb[j] # can be incremented j = k - 1 while j >= 0 and comb[j] == R - k + j + 1: j -= 1 # If j is negative, we have generated all # possible combinations if j < 0: break comb[j] += 1 # Increment comb[j] and adjust the remaining # elements of the combination for i in range(j+1, k): comb[i] = comb[i-1] + 1 # Return the minimum XOR value return min_xorL, R, K = 1, 10, 3# Find the minimum bitwise XOR of at most K integer# between [L, R]min_xor = min_bitwise_xor(L, R, K)# print the resultprint(min_xor)# This code is Contributed by Shushant Kumar |
Java
import java.util.*;public class Main { public static int minBitwiseXor(int L, int R, int K) { int minXor = Integer.MAX_VALUE; // Iterate over all possible values of k from 1 to K for (int k = 1; k <= K; k++) { // Initialize a list to store the current combination List<Integer> comb = new ArrayList<Integer>(); // Initialize the first k elements of the combination to L, L+1, ..., L+k-1 for (int i = 0; i < k; i++) { comb.add(L + i); } // Generate all possible combinations of k integers between L and R while (comb.get(k - 1) <= R) { // Calculate the XOR value of the current combination int xorVal = 0; for (int num : comb) { xorVal ^= num; } // Update the minimum XOR value if necessary minXor = Math.min(minXor, xorVal); // Check if we have reached the end of the range [L, R] if (comb.get(k - 1) == R) { break; } // Find the rightmost index j such that comb[j] can be incremented int j = k - 1; while (j >= 0 && comb.get(j) == R - k + j + 1) { j--; } // If j is negative, we have generated all possible combinations if (j < 0) { break; } // Increment comb[j] and adjust the remaining elements of the combination comb.set(j, comb.get(j) + 1); for (int i = j + 1; i < k; i++) { comb.set(i, comb.get(i - 1) + 1); } } } // Return the minimum XOR value return minXor; } public static void main(String[] args) { int L = 1, R = 10, K = 3; // Find the minimum bitwise XOR of at most K integers between [L, R] int minXor = minBitwiseXor(L, R, K); // Print the result System.out.println(minXor); }}// This code is contributed by Shushant Kumar |
C#
using System;class Program { // Function to find the minimum bitwise XOR of at most K // integers between [L, R] static int MinBitwiseXOR(int L, int R, int K) { // Initialize the minimum XOR value to a large // number int min_xor = int.MaxValue; // Iterate over all possible values of k from 1 to K for (int k = 1; k <= K; k++) { // Initialize an array to store the current // combination int[] comb = new int[k]; // Initialize the first k elements of the // combination to L, L+1, ..., L+k-1 for (int i = 0; i < k; i++) { comb[i] = L + i; } // Generate all possible combinations of k // integers between L and R while (comb[k - 1] <= R) { // Calculate the XOR value of the current // combination int xor_val = 0; foreach(int num in comb) { xor_val ^= num; } // Update the minimum XOR value if necessary min_xor = Math.Min(min_xor, xor_val); // Check if we have reached the end of the // range [L, R] if (comb[k - 1] == R) { break; } // Find the rightmost index j such that // comb[j] can be incremented int j = k - 1; while (j >= 0 && comb[j] == R - k + j + 1) { j--; } // If j is negative, we have generated all // possible combinations if (j < 0) { break; } // Increment comb[j] and adjust the // remaining elements of the combination comb[j]++; for (int i = j + 1; i < k; i++) { comb[i] = comb[i - 1] + 1; } } } // Return the minimum XOR value return min_xor; } static void Main(string[] args) { int L = 1, R = 10, K = 3; // Find the minimum bitwise XOR of at most K // integers between [L, R] int min_xor = MinBitwiseXOR(L, R, K); // Print the result Console.WriteLine(min_xor); }} |
Javascript
// This function finds the minimum XOR value of at most K integers between L and Rfunction minBitwiseXor(L, R, K){// Initialize the minimum XOR value to the maximum integer valuelet minXor = Number.MAX_SAFE_INTEGER;// Iterate over all possible values of k from 1 to Kfor (let k = 1; k <= K; k++){ // Initialize an array to store the current combination let comb = []; // Initialize the first k elements of the combination to L, L+1, ..., L+k-1 for (let i = 0; i < k; i++) { comb.push(L + i); } // Generate all possible combinations of k integers between L and R while (comb[k - 1] <= R) { // Calculate the XOR value of the current combination let xorVal = 0; for (let num of comb) { xorVal ^= num; } // Update the minimum XOR value if necessary minXor = Math.min(minXor, xorVal); // Check if we have reached the end of the range [L, R] if (comb[k - 1] == R) { break; } // Find the rightmost index j such that comb[j] can be incremented let j = k - 1; while (j >= 0 && comb[j] == R - k + j + 1) { j--; } // If j is negative, we have generated all possible combinations if (j < 0) { break; } // Increment comb[j] and adjust the remaining elements of the combination comb[j]++; for (let i = j + 1; i < k; i++) { comb[i] = comb[i - 1] + 1; } }}// Return the minimum XOR valuereturn minXor;}// Test the function with example valueslet L = 1;let R = 10;let K = 3;let minXor = minBitwiseXor(L, R, K);// Print the resultconsole.log(minXor);//This code is written by Sundaram |
Output
0
Time Complexity: O((R-L+1)^K * K^2), where R-L+1 is the number of integers between L and R, and K is the maximum number of integers that can be selected.
Space Complexity: O(K)
Efficient Approach: An observation that helps us in solving the problem is the Bitwise XOR of two numbers X and (X+1) is 1 if X is an even number. Thus, the Bitwise XOR of four consecutive numbers would be 0 if the first one is even.
Follow the steps below to solve the problem:
- If the value of K is greater than 4 then the answer is always 0. (This is because four numbers X, (X+1), (X+2), and (X+3) can always be found in a range of 5 where X is an even number.)
- If the value of K is 2, call the function func2() that takes L, R, and K as input parameters and does the following:
- If the value of (R-L) is greater than or equal to 2 i.e. there are at least 3 numbers in the range, return 1.(This is because two numbers X and X+1 can always be found in a range of 3 where X is an even number.)
- Otherwise, return the minimum of L and (L^R).
- If the value of K is 3, call the function func3() that takes L, R, and K as input parameters and does the following:
- If (R^L) lies between L and R, return 0. (This is because (R^L)^L^R=0) )
- Otherwise, return func2(L, R, K)
- If the value of K is 4, call the function func4() that takes L, R, and K as input parameters and does the following:
- If (R-L) is greater than or equal to 4, i.e. there are at least 5 numbers in the range, return 0. (This is because four numbers X,(X+1),(X+2), and (X+3) can always be found in a range of 5 where X is an even number.)
- Otherwise, return the minimum of Xor of the four numbers in the range [L, R] and func3(L, R, K).
- Otherwise, return L.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function for K=2int func2(int L, int R, int K){ if (R - L >= 2) return 1; return min(L, L ^ R);}// Function for K=2int func3(int L, int R, int K){ if ((R ^ L) > L && (R ^ L) < R) return 0; return func2(L, R, K);}// Function for K=2int func4(int L, int R, int K){ if (R - L >= 4) return 0; int minval = L ^ (L + 1) ^ (L + 2) ^ (L + 3); return min(minval, func3(L, R, K));}// Function to calculate the minimum XOR of at most K// elements in [L, R]int minimumXor(int L, int R, int K){ if (K > 4) return 0; else if (K == 4) return func4(L, R, K); else if (K == 3) return func3(L, R, K); else if (K == 2) return func2(L, R, K); else return L;}// Driver codeint main(){ // Input int L = 1, R = 3, K = 3; // Function call cout << minimumXor(L, R, K) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG {// Function for K=2static int func2(int L, int R, int K){ if (R - L >= 2) return 1; return Math.min(L, L ^ R);} // Function for K=2static int func3(int L, int R, int K){ if ((R ^ L) > L && (R ^ L) < R) return 0; return func2(L, R, K);} // Function for K=2static int func4(int L, int R, int K){ if (R - L >= 4) return 0; int minval = L ^ (L + 1) ^ (L + 2) ^ (L + 3); return Math.min(minval, func3(L, R, K));}// Function to calculate the minimum XOR of at most K// elements in [L, R]static int minimumXor(int L, int R, int K){ if (K > 4) return 0; else if (K == 4) return func4(L, R, K); else if (K == 3) return func3(L, R, K); else if (K == 2) return func2(L, R, K); else return L;} // Driver code public static void main(String[] args) { // Input int L = 1, R = 3, K = 3; // Function call System.out.println( minimumXor(L, R, K)); }}// This code is contributed by sanjoy_62. |
Python3
# Python program for the above approach# Function for K=2def func2(L, R, K): if (R - L >= 2): return 1 return min(L, L ^ R) # Function for K=2def func3(L, R, K): if ((R ^ L) > L and (R ^ L) < R): return 0 return func2(L, R, K) # Function for K=2def func4(L, R, K): if (R - L >= 4): return 0 minval = L ^ (L + 1) ^ (L + 2) ^ (L + 3) return min(minval, func3(L, R, K)) # Function to calculate the minimum XOR of at most K# elements in [L, R]def minimumXor(L, R, K): if (K > 4): return 0 elif (K == 4): return func4(L, R, K) elif (K == 3): return func3(L, R, K) elif (K == 2): return func2(L, R, K) else: return L# Driver codeif __name__ == '__main__': # Input L, R, K = 1, 3, 3 # Function call print (minimumXor(L, R, K))# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{// Function for K=2static int func2(int L, int R, int K){ if (R - L >= 2) return 1; return Math.Min(L, L ^ R);} // Function for K=2static int func3(int L, int R, int K){ if ((R ^ L) > L && (R ^ L) < R) return 0; return func2(L, R, K);} // Function for K=2static int func4(int L, int R, int K){ if (R - L >= 4) return 0; int minval = L ^ (L + 1) ^ (L + 2) ^ (L + 3); return Math.Min(minval, func3(L, R, K));}// Function to calculate the minimum XOR of at most K// elements in [L, R]static int minimumXor(int L, int R, int K){ if (K > 4) return 0; else if (K == 4) return func4(L, R, K); else if (K == 3) return func3(L, R, K); else if (K == 2) return func2(L, R, K); else return L;}// Driver codestatic void Main(){ // Input int L = 1, R = 3, K = 3; // Function call Console.Write( minimumXor(L, R, K));}}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript program for the above approach// Function for K=2function func2(L, R, K){ if (R - L >= 2) return 1; return Mat.min(L, L ^ R);}// Function for K=2function func3(L, R, K){ if ((R ^ L) > L && (R ^ L) < R) return 0; return func2(L, R, K);}// Function for K=2function func4(L, R, K){ if (R - L >= 4) return 0; var minval = L ^ (L + 1) ^ (L + 2) ^ (L + 3); return Math.min(minval, func3(L, R, K));}// Function to calculate the minimum XOR // of at most K elements in [L, R]function minimumXor(L, R, K){ if (K > 4) return 0; else if (K == 4) return func4(L, R, K); else if (K == 3) return func3(L, R, K); else if (K == 2) return func2(L, R, K); else return L;}// Driver code// Inputvar L = 1, R = 3, K = 3;// Function calldocument.write(minimumXor(L, R, K));// This code is contributed by SURENDRA_GANGWAR</script> |
Output
0
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
