Given an array arr[] and Q queries, the task is to find the resulting updated array after Q queries. There are two types of queries and the following operation is performed by them:
- Update(L, R, K): Perform XOR for each element within the range L to R with K.
- Display(): Display the current state of the given array.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6}, Q = 2
Query 1: Update(1, 5, 3)
Query 2: Display()
Output: 2 1 0 7 6 6
Explanation:
The update query performs XOR of all elements in the range [1, 5].
After performing the update query, the above array is displayed for display query because:
1 ^ 3 = 2
2 ^ 3 = 1
3 ^ 3 = 0
4 ^ 3 = 7
5 ^ 3 = 6
Input: arr[] = {2, 4, 6, 8, 10}, Q = 3
Query 1: Update(1, 3, 2)
Query 2: Update(2, 4, 3)
Query 3: Display()
Output: 0 5 7 11 10
Explanation:
There are two update queries.
After performing the first update query, the given array is changed to {0, 6, 4, 8, 10}. This is because:
2 ^ 2 = 0
4 ^ 2 = 6
6 ^ 2 = 4
After obtaining this array, this array further gets changed for the second query as the {0, 5, 7, 11, 10}. This is because:
6 ^ 3 = 5
4 ^ 3 = 7
8 ^ 3 = 11
Naive Approach: The naive approach for this problem is for every update query, run a loop from L to R and perform the XOR operation with the given K with all the elements from arr[L] to arr[R]. In order to perform the display query, simply print the array arr[]. The time complexity for this approach is O(NQ) where N is the length of the array and Q is the number of queries.
Efficient Approach: The idea is to use a kadane’s algorithm for this problem.
- An empty array res[] is defined with the same length as the original array.
- For every update query {L, R, K}, the res[] array is modified as:
- XOR K to res[L]
- XOR K to res[R + 1]
- Whenever the user gives a display query:
- Initialize a counter variable ‘i’ to the index 1.
- Perform the operation:
res[i] = res[i] ^ res[i - 1]
- Initialize a counter variable ‘i’ to the index 0.
- For every index in the array’s the required answer is:
arr[i] ^ res[i]
Below is the implementation of the above approach:
C++
// C++ implementation to perform the// XOR range updates on an array#include <bits/stdc++.h>using namespace std;// Function to perform the update operation// on the given arrayvoid update(int res[], int L, int R, int K){ // Converting the indices to // 0 indexing. L -= 1; R -= 1; // Saving the XOR of K from the starting // index in the range [L, R]. res[L] ^= K; // Saving the XOR of K at the ending index // in the given [L, R]. res[R + 1] ^= K;}// Function to display the resulting arrayvoid display(int arr[], int res[], int n){ for (int i = 1; i < n; i++) { // Finding the resultant value in the // result array res[i] = res[i] ^ res[i - 1]; } for (int i = 0; i < n; i++) { // Combining the effects of the updates // with the original array without // changing the initial array. cout << (arr[i] ^ res[i]) << " "; } cout << endl;}// Driver codeint main(){ int arr[] = { 2, 4, 6, 8, 10 }; int N = sizeof(arr) / sizeof(arr[0]); int res[N]; memset(res, 0, sizeof(res)); // Query 1 int L = 1, R = 3, K = 2; update(res, L, R, K); // Query 2 L = 2; R = 4; K = 3; update(res, L, R, K); // Query 3 display(arr, res, N); return 0;} |
Java
// Java implementation to perform the// XOR range updates on an arrayclass GFG{ // Function to perform the update // operation on the given arraystatic void update(int res[], int L, int R, int K){ // Converting the indices to // 0 indexing. L -= 1; R -= 1; // Saving the XOR of K from the // starting index in the range [L, R]. res[L] ^= K; // Saving the XOR of K at the ending // index in the given [L, R]. res[R + 1] ^= K;}// Function to display the resulting arraystatic void display(int arr[], int res[], int n){ int i; for(i = 1; i < n; i++) { // Finding the resultant value // in the result array res[i] = res[i] ^ res[i - 1]; } for(i = 0; i < n; i++) { // Combining the effects of the // updates with the original array // without changing the initial array. System.out.print((arr[i] ^ res[i]) + " "); } System.out.println();}// Driver codepublic static void main(String []args){ int arr[] = { 2, 4, 6, 8, 10 }; int N = arr.length; int res[] = new int[N]; // Query 1 int L = 1, R = 3, K = 2; update(res, L, R, K); // Query 2 L = 2; R = 4; K = 3; update(res, L, R, K); // Query 3 display(arr, res, N);}}// This code is contributed by chitranayal |
Python3
# Python3 implementation to perform the # XOR range updates on an array # Function to perform the update operation # on the given array def update(res, L, R, K): # Converting the indices to # 0 indexing. L = L - 1 R = R - 1 # Saving the XOR of K from the starting # index in the range [L, R]. res[L] = res[L] ^ K # Saving the XOR of K at the ending index # in the given [L, R]. res[R + 1] = res[R + 1] ^ K# Function to display the resulting array def display(arr, res, n): for i in range(1, n): # Finding the resultant value in the # result array res[i] = res[i] ^ res[i - 1] for i in range(0, n): # Combining the effects of the updates # with the original array without # changing the initial array. print (arr[i] ^ res[i], end = " ")# Driver code arr = [ 2, 4, 6, 8, 10 ] N = len(arr) res = [0] * N# Query 1 L = 1R = 3K = 2update(res, L, R, K) # Query 2 L = 2R = 4K = 3update(res, L, R, K) # Query 3 display(arr, res, N)# This code is contributed by Pratik Basu |
C#
// C# implementation to perform the// XOR range updates on an arrayusing System;class GFG{ // Function to perform the update // operation on the given arraystatic void update(int []res, int L, int R, int K){ // Converting the indices to // 0 indexing. L -= 1; R -= 1; // Saving the XOR of K from the // starting index in the range [L, R]. res[L] ^= K; // Saving the XOR of K at the ending // index in the given [L, R]. res[R + 1] ^= K;}// Function to display the resulting arraystatic void display(int []arr, int []res, int n){ int i; for(i = 1; i < n; i++) { // Finding the resultant value // in the result array res[i] = res[i] ^ res[i - 1]; } for(i = 0; i < n; i++) { // Combining the effects of the // updates with the original array // without changing the initial array. Console.Write((arr[i] ^ res[i]) + " "); } Console.WriteLine();}// Driver codepublic static void Main(){ int []arr = { 2, 4, 6, 8, 10 }; int N = arr.Length; int []res = new int[N]; // Query 1 int L = 1, R = 3, K = 2; update(res, L, R, K); // Query 2 L = 2; R = 4; K = 3; update(res, L, R, K); // Query 3 display(arr, res, N);}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript implementation to perform the// XOR range updates on an array// Function to perform the update // operation on the given arrayfunction update(res, L, R, K){ // Converting the indices to // 0 indexing. L -= 1; R -= 1; // Saving the XOR of K from the // starting index in the range [L, R]. res[L] ^= K; // Saving the XOR of K at the ending // index in the given [L, R]. res[R + 1] ^= K;} // Function to display the resulting arrayfunction display(arr, res, n){ let i; for(i = 1; i < n; i++) { // Finding the resultant value // in the result array res[i] = res[i] ^ res[i - 1]; } for(i = 0; i < n; i++) { // Combining the effects of the // updates with the original array // without changing the initial array. document.write((arr[i] ^ res[i]) + " "); } document.write( "<br/>");} // Driver Code let arr = [ 2, 4, 6, 8, 10 ]; let N = arr.length; let res = Array.from({length: N}, (_, i) => 0); // Query 1 let L = 1, R = 3, K = 2; update(res, L, R, K); // Query 2 L = 2; R = 4; K = 3; update(res, L, R, K); // Query 3 display(arr, res, N); </script> |
Output:
0 5 7 11 10
Time Complexity:
- The time complexity for the update is O(1).
- The time complexity for displaying the array is O(N).
Auxiliary Space: O(N)
Note: This approach works very well when the update queries are very high compared to the display queries.
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!
