Given a binary array arr[] of size N and some queries. Each query represents an index range [l, r]. The task is to find the xor of the elements in the given index range for each query i.e. arr[l] ^ arr[l + 1] ^ … ^ arr[r].
Examples:
Input: arr[] = {1, 0, 1, 1, 0, 1, 1}, q[][] = {{0, 3}, {0, 2}}
Output:
1
0
Query 1: arr[0] ^ arr[1] ^ arr[2] ^ arr[3] = 1 ^ 0 ^ 1 ^ 1 = 1
Query 1: arr[0] ^ arr[1] ^ arr[2] = 1 ^ 0 ^ 1 = 0Input: arr[] = {1, 0, 1, 1, 0, 1, 1}, q[][] = {{1, 1}}
Output: 0
Approach: The main observation is that the required answer will always be either 0 or 1. If the number of 1’s in the given range are odd then the answer will be 1. Otherwise 0. To answer multiple queries in constant time, use a prefix sum array pre[] where pre[i] stores the number of 1’s in the original array in the index range [0, i] which can be used to find the number of 1’s in any index range of the given array.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return Xor in a range// of a binary arrayint xorRange(int pre[], int l, int r){ // To store the count of 1s int cntOnes = pre[r]; if (l - 1 >= 0) cntOnes -= pre[l - 1]; // If number of ones are even if (cntOnes % 2 == 0) return 0; // If number of ones are odd else return 1;}// Function to perform the queriesvoid performQueries(int queries[][2], int q, int a[], int n){ // To store prefix sum int pre[n]; // pre[i] stores the number of // 1s from pre[0] to pre[i] pre[0] = a[0]; for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + a[i]; // Perform queries for (int i = 0; i < q; i++) cout << xorRange(pre, queries[i][0], queries[i][1]) << endl;}// Driver codeint main(){ int a[] = { 1, 0, 1, 1, 0, 1, 1 }; int n = sizeof(a) / sizeof(a[0]); // Given queries int queries[][2] = { { 0, 3 }, { 0, 2 } }; int q = sizeof(queries) / sizeof(queries[0]); performQueries(queries, q, a, n); return 0;} |
Java
// Java implementation of the approach import java.util.*;class GFG{// Function to return Xor in a range// of a binary arraystatic int xorRange(int pre[], int l, int r){ // To store the count of 1s int cntOnes = pre[r]; if (l - 1 >= 0) cntOnes -= pre[l - 1]; // If number of ones are even if (cntOnes % 2 == 0) return 0; // If number of ones are odd else return 1;}// Function to perform the queriesstatic void performQueries(int queries[][], int q, int a[], int n){ // To store prefix sum int []pre = new int[n]; // pre[i] stores the number of // 1s from pre[0] to pre[i] pre[0] = a[0]; for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + a[i]; // Perform queries for (int i = 0; i < q; i++) System.out.println(xorRange(pre, queries[i][0], queries[i][1]));}// Driver codepublic static void main(String[] args) { int a[] = { 1, 0, 1, 1, 0, 1, 1 }; int n = a.length; // Given queries int queries[][] = { { 0, 3 }, { 0, 2 } }; int q = queries.length; performQueries(queries, q, a, n);}}// This code is contributed by Princi Singh |
Python3
# Python3 implementation of the approach# Function to return Xor in a range# of a binary arraydef xorRange(pre, l, r): # To store the count of 1s cntOnes = pre[r] if (l - 1 >= 0): cntOnes -= pre[l - 1] # If number of ones are even if (cntOnes % 2 == 0): return 0 # If number of ones are odd else: return 1# Function to perform the queriesdef performQueries(queries, q, a, n): # To store prefix sum pre = [0 for i in range(n)] # pre[i] stores the number of # 1s from pre[0] to pre[i] pre[0] = a[0] for i in range(1, n): pre[i] = pre[i - 1] + a[i] # Perform queries for i in range(q): print(xorRange(pre, queries[i][0], queries[i][1]))# Driver codea = [ 1, 0, 1, 1, 0, 1, 1 ]n = len(a)# Given queriesqueries = [[ 0, 3 ], [ 0, 2 ]]q = len(queries)performQueries(queries, q, a, n)# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System;class GFG{// Function to return Xor in a range// of a binary arraystatic int xorRange(int []pre, int l, int r){ // To store the count of 1s int cntOnes = pre[r]; if (l - 1 >= 0) cntOnes -= pre[l - 1]; // If number of ones are even if (cntOnes % 2 == 0) return 0; // If number of ones are odd else return 1;}// Function to perform the queriesstatic void performQueries(int [,]queries, int q, int []a, int n){ // To store prefix sum int []pre = new int[n]; // pre[i] stores the number of // 1s from pre[0] to pre[i] pre[0] = a[0]; for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + a[i]; // Perform queries for (int i = 0; i < q; i++) Console.WriteLine(xorRange(pre, queries[i, 0], queries[i, 1]));}// Driver codepublic static void Main() { int []a = { 1, 0, 1, 1, 0, 1, 1 }; int n = a.Length; // Given queries int [,]queries = { { 0, 3 }, { 0, 2 } }; int q = queries.Length; performQueries(queries, q, a, n);}}// This code is contributed// by Akanksha Rai |
Javascript
<script>// Javascript implementation of the approach// Function to return Xor in a range// of a binary arrayfunction xorRange(pre, l, r){ // To store the count of 1s let cntOnes = pre[r]; if (l - 1 >= 0) cntOnes -= pre[l - 1]; // If number of ones are even if (cntOnes % 2 == 0) return 0; // If number of ones are odd else return 1;}// Function to perform the queriesfunction performQueries(queries, q, a, n){ // To store prefix sum let pre = new Array(n); // pre[i] stores the number of // 1s from pre[0] to pre[i] pre[0] = a[0]; for (let i = 1; i < n; i++) pre[i] = pre[i - 1] + a[i]; // Perform queries for (let i = 0; i < q; i++) document.write(xorRange(pre, queries[i][0], queries[i][1]) + "<br>");}// Driver code let a = [ 1, 0, 1, 1, 0, 1, 1 ]; let n = a.length; // Given queries let queries = [ [ 0, 3 ], [ 0, 2 ] ]; let q = queries.length; performQueries(queries, q, a, n);</script> |
Output:
1 0
Time Complexity: O(n + q), where n is the size of the given array and q is the number of queries given.
Auxiliary Space: O(n), where n is the size of the given array
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!
