Given an array integer arr[] of size N and Q queries. Each query is of the form (L, R), where L and R are indices of the array. The task is to find the XOR value of the subarray arr[L…R].
Examples:
Input: arr[] = {2, 5, 1, 6, 1, 2, 5} query[] = {{1, 4}}
Output: 3
The XOR value of arr[1…4] is 3.Input: arr[] = {2, 5, 1, 6, 1, 2, 5} query[] = {{0, 6}}
Output: 6
The XOR value of arr[0…6] is 6.
O(N) auxiliary space approach: Please refer to this article for the O(N) auxiliary space approach.
Approach: Here we will discuss a constant space solution, but we will modify the input array.
1. Update the input array from index 1 to N – 1, such that arr[i] stores the XOR from arr[0] to arr[i].
arr[i] = XOR(arr[0], arr[1], .., arr[i])
2. To process a query from L to R just return arr[L-1] ^ arr[R].
For example:
Consider the example: arr[] = { 3, 2, 4, 5, 1, 1, 5, 3 }, query[] = {{1, 4 }, { 3, 7}}
After taking the XOR of consecutive elements, arr[] = {3, 1, 5, 0, 1, 0, 5, 6}
For first query {1, 4} ans = arr[0] ^ arr[4] = 3 ^ 1 = 2
For the second query {3, 7} ans = arr[2] ^ arr[7] = 5 ^ 6 = 3
Below is the implementation of the above approach:
C++
// C++ program to find XOR // in a range from L to R #include <bits/stdc++.h> using namespace std; // Function to find XOR // in a range from L to R void find_Xor( int arr[], pair< int , int > query[], int N, int Q) { // Compute xor from arr[0] to arr[i] for ( int i = 1; i < N; i++) { arr[i] = arr[i] ^ arr[i - 1]; } int ans = 0; // process every query // in constant time for ( int i = 0; i < Q; i++) { // if L==0 if (query[i].first == 0) ans = arr[query[i].second]; else ans = arr[query[i].first - 1] ^ arr[query[i].second]; cout << ans << endl; } } // Driver Code int main() { int arr[] = { 3, 2, 4, 5, 1, 1, 5, 3 }; int N = 8; int Q = 2; pair< int , int > query[Q] = { { 1, 4 }, { 3, 7 } }; // query[] find_Xor(arr, query, N, Q); return 0; } |
Java
// Java program to find XOR // in a range from L to R class GFG{ static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to find XOR // in a range from L to R static void find_Xor( int arr[], pair query[], int N, int Q) { // Compute xor from arr[0] to arr[i] for ( int i = 1 ; i < N; i++) { arr[i] = arr[i] ^ arr[i - 1 ]; } int ans = 0 ; // Process every query // in constant time for ( int i = 0 ; i < Q; i++) { // If L==0 if (query[i].first == 0 ) ans = arr[query[i].second]; else ans = arr[query[i].first - 1 ] ^ arr[query[i].second]; System.out.print(ans + "\n" ); } } // Driver Code public static void main(String[] args) { int arr[] = { 3 , 2 , 4 , 5 , 1 , 1 , 5 , 3 }; int N = 8 ; int Q = 2 ; pair query[] = { new pair( 1 , 4 ), new pair( 3 , 7 ) }; // query[] find_Xor(arr, query, N, Q); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 program to find XOR # in a range from L to R # Function to find XOR # in a range from L to R def find_Xor(arr, query, N, Q): # Compute xor from arr[0] to arr[i] for i in range ( 1 , N): arr[i] = arr[i] ^ arr[i - 1 ] ans = 0 # Process every query # in constant time for i in range (Q): # If L == 0 if query[i][ 0 ] = = 0 : ans = arr[query[i][ 1 ]] else : ans = (arr[query[i][ 0 ] - 1 ] ^ arr[query[i][ 1 ]]) print (ans) # Driver code def main(): arr = [ 3 , 2 , 4 , 5 , 1 , 1 , 5 , 3 ] N = 8 Q = 2 # query[] query = [ [ 1 , 4 ], [ 3 , 7 ] ] find_Xor(arr, query, N, Q) main() # This code is contributed by Stuti Pathak |
C#
// C# program to find XOR // in a range from L to R using System; class GFG{ class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to find XOR // in a range from L to R static void find_Xor( int []arr, pair []query, int N, int Q) { // Compute xor from arr[0] to arr[i] for ( int i = 1; i < N; i++) { arr[i] = arr[i] ^ arr[i - 1]; } int ans = 0; // Process every query // in constant time for ( int i = 0; i < Q; i++) { // If L==0 if (query[i].first == 0) ans = arr[query[i].second]; else ans = arr[query[i].first - 1] ^ arr[query[i].second]; Console.Write(ans + "\n" ); } } // Driver Code public static void Main(String[] args) { int []arr = { 3, 2, 4, 5, 1, 1, 5, 3 }; int N = 8; int Q = 2; pair []query = { new pair(1, 4), new pair(3, 7) }; // query[] find_Xor(arr, query, N, Q); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find XOR // in a range from L to R // Function to find XOR // in a range from L to R function find_Xor(arr, query, N, Q) { // Compute xor from arr[0] to arr[i] for ( var i = 1; i < N; i++) { arr[i] = arr[i] ^ arr[i - 1]; } var ans = 0; // process every query // in constant time for ( var i = 0; i < Q; i++) { // if L==0 if (query[i][0] == 0) ans = arr[query[i][1]]; else ans = arr[query[i][0] - 1] ^ arr[query[i][1]]; document.write( ans + "<br>" ); } } // Driver Code var arr = [3, 2, 4, 5, 1, 1, 5, 3]; var N = 8; var Q = 2; var query = [[1, 4], [3, 7]]; // query[] find_Xor(arr, query, N, Q); </script> |
2 3
Time Complexity: O (N + Q)
Auxiliary Space: O (1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!