Given an array, arr[] of N positive integers and M queries which consist of two integers [Li, Ri] where 1 ? Li ? Ri ? N. For each query, find the number of subarrays in range [Li, Ri] for which (X+1)=(X?1) where X denotes the xor of a subarray.
Input: arr[]= {1, 2, 9, 8, 7}, queries[] = {{1, 5}, {3, 4}}
Output: 6 1
Explanation:
Query 1: L=1, R=5: subarrays [1, 3], [1, 4], [2, 2], [2, 5], [3, 5], [4, 4]
Query 2: L=3, R=4: subarray [4, 4]Input: arr[] = {1, 2, 2, 4, 5}, queries[] = {{2, 4}, {3, 5}}
Output: 6 3
Naive approach: For each query, select the given range [Li, Ri] and for each subarray check if it satisfies the given condition.
Time complexity: O(N3 * M)
Efficient approach: In the above problem, the following observations can be made:
- To satisfy the given condition, X must be an even number because
- If X is even, (X?1)=(X+1)
- If X is odd, (X?1)=(X?1)
- For a subarray, its xor will be even if the count of odd numbers in that subarray is even.
- If the count of odd numbers is even, then the sum of the subarray will be even. So, the subarrays with an even sum are the answer to this problem.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;vector<int> countXorSubarr( vector<int> arr, vector<vector<int> > queries, int n, int m){ // As queries are in 1-based indexing, // add one dummy entry in beginning // of arr to make it 1-indexed arr.insert(arr.begin(), 0); // sum[] will contain parity // of prefix sum till index i // count[] will contain // number of 0s in sum[] int count[n + 1], sum[n + 1]; count[0] = sum[0] = 0; for (int i = 1; i <= n; i++) { // Take the parity of current sum sum[i] = (sum[i - 1] + arr[i]) % 2; count[i] = count[i - 1]; // If current parity is even, // increase the count if (sum[i] % 2 == 0) count[i]++; } // Array to hold the answer of 'm' queries vector<int> ans; // Iterate through queries and use handshake // lemma to count even sum subarrays // ( Note that an even sum can // be formed by two even or two odd ) for (vector<int> qu : queries) { int L = qu[0], R = qu[1]; // Find count of even and // odd sums in range [L, R] int even = count[R] - count[L - 1]; int odd = (R - L + 1) - even; // If prefix sum at L-1 is odd, // then we need to swap // our counts of odd and even if (sum[L - 1] == 1) swap(even, odd); // Taking no element is also // considered an even sum // so even will be increased by 1 // (This is the condition when // a prefix of even sum is taken) even++; // Find number of ways to // select two even's or two odd's int subCount = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2; ans.push_back(subCount); } return ans;}// Driver codeint main(){ int n = 5; vector<int> arr = { 1, 2, 9, 8, 7 }; int m = 2; vector<vector<int> > queries = { { 1, 5 }, { 3, 4 } }; // Function call and print answer vector<int> ans = countXorSubarr(arr, queries, n, m); for (int x : ans) cout << x << " "; cout << endl; return 0;} |
Java
// Java program for the above approachimport java.util.ArrayList;class GFG{ public static ArrayList<Integer> countXorSubarr(int[] arr, int[][] queries, int n, int m) { // As queries are in 1-based indexing, // add one dummy entry in beginning // of arr to make it 1-indexed // arr.insert(arr.begin(), 0); int[] temp_arr = new int[arr.length + 1]; temp_arr[0] = 0; for (int i = 1; i < temp_arr.length; i++) { temp_arr[i] = arr[i - 1]; } arr = temp_arr.clone(); // sum[] will contain parity // of prefix sum till index i // count[] will contain // number of 0s in sum[] int[] count = new int[n + 1]; int[] sum = new int[n + 1]; count[0] = sum[0] = 0; for (int i = 1; i <= n; i++) { // Take the parity of current sum sum[i] = (sum[i - 1] + arr[i]) % 2; count[i] = count[i - 1]; // If current parity is even, // increase the count if (sum[i] % 2 == 0) count[i]++; } // Array to hold the answer of 'm' queries ArrayList<Integer> ans = new ArrayList<Integer>(); // Iterate through queries and use handshake // lemma to count even sum subarrays // ( Note that an even sum can // be formed by two even or two odd ) for (int[] qu : queries) { int L = qu[0], R = qu[1]; // Find count of even and // odd sums in range [L, R] int even = count[R] - count[L - 1]; int odd = (R - L + 1) - even; // If prefix sum at L-1 is odd, // then we need to swap // our counts of odd and even if (sum[L - 1] == 1) { int temp = even; even = odd; odd = temp; } // Taking no element is also // considered an even sum // so even will be increased by 1 // (This is the condition when // a prefix of even sum is taken) even++; // Find number of ways to // select two even's or two odd's int subCount = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2; ans.add(subCount); } return ans; } // Driver code public static void main(String args[]) { int n = 5; int[] arr = { 1, 2, 9, 8, 7 }; int m = 2; int[][] queries = { { 1, 5 }, { 3, 4 } }; // Function call and print answer ArrayList<Integer> ans = countXorSubarr(arr, queries, n, m); for (int x : ans) System.out.print(x + " "); System.out.println(""); }}// This code is contributed by saurabh_jaiswal. |
Python3
# python program for the above approachimport mathdef countXorSubarr(arr, queries, n, m): # As queries are in 1-based indexing, # add one dummy entry in beginning # of arr to make it 1-indexed arr.insert(0, 0) # sum[] will contain parity # of prefix sum till index i # count[] will contain # number of 0s in sum[] count = [0 for _ in range(n + 1)] sum = [0 for _ in range(n + 1)] for i in range(1, n+1): # Take the parity of current sum sum[i] = (sum[i - 1] + arr[i]) % 2 count[i] = count[i - 1] # If current parity is even, # increase the count if (sum[i] % 2 == 0): count[i] += 1 # Array to hold the answer of 'm' queries ans = [] # Iterate through queries and use handshake # lemma to count even sum subarrays # ( Note that an even sum can # be formed by two even or two odd ) for qu in queries: L = qu[0] R = qu[1] # Find count of even and # odd sums in range [L, R] even = count[R] - count[L - 1] odd = (R - L + 1) - even # If prefix sum at L-1 is odd, # then we need to swap # our counts of odd and even if (sum[L - 1] == 1): temp = even even = odd odd = temp # Taking no element is also # considered an even sum # so even will be increased by 1 # (This is the condition when # a prefix of even sum is taken) even += 1 # Find number of ways to # select two even's or two odd's subCount = (even * (even - 1)) // 2 + (odd * (odd - 1)) // 2 ans.append(subCount) return ans# Driver codeif __name__ == "__main__": n = 5 arr = [1, 2, 9, 8, 7] m = 2 queries = [[1, 5], [3, 4]] # Function call and print answer ans = countXorSubarr(arr, queries, n, m) for x in ans: print(x, end=" ") # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ public static List<int> countXorSubarr(int[] arr, int[,] queries, int n, int m) { // As queries are in 1-based indexing, // add one dummy entry in beginning // of arr to make it 1-indexed // arr.insert(arr.begin(), 0); int[] temp_arr = new int[arr.Length + 1]; temp_arr[0] = 0; for (int i = 1; i < temp_arr.Length; i++) { temp_arr[i] = arr[i - 1]; } arr = temp_arr; // sum[] will contain parity // of prefix sum till index i // []count will contain // number of 0s in sum[] int[] count = new int[n + 1]; int[] sum = new int[n + 1]; count[0] = sum[0] = 0; for (int i = 1; i <= n; i++) { // Take the parity of current sum sum[i] = (sum[i - 1] + arr[i]) % 2; count[i] = count[i - 1]; // If current parity is even, // increase the count if (sum[i] % 2 == 0) count[i]++; } // Array to hold the answer of 'm' queries List<int> ans = new List<int>(); // Iterate through queries and use handshake // lemma to count even sum subarrays // ( Note that an even sum can // be formed by two even or two odd ) for(int i = 0; i < queries.GetLength(0); i++) { int L = queries[i,0], R = queries[i,1]; // Find count of even and // odd sums in range [L, R] int even = count[R] - count[L - 1]; int odd = (R - L + 1) - even; // If prefix sum at L-1 is odd, // then we need to swap // our counts of odd and even if (sum[L - 1] == 1) { int temp = even; even = odd; odd = temp; } // Taking no element is also // considered an even sum // so even will be increased by 1 // (This is the condition when // a prefix of even sum is taken) even++; // Find number of ways to // select two even's or two odd's int subCount = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2; ans.Add(subCount); } return ans; } public static int[] GetRow(int[,] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int[rowLength]; for (var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i]; return rowVector; } // Driver code public static void Main(String []args) { int n = 5; int[] arr = { 1, 2, 9, 8, 7 }; int m = 2; int[,] queries = { { 1, 5 }, { 3, 4 } }; // Function call and print answer List<int> ans = countXorSubarr(arr, queries, n, m); foreach (int x in ans) Console.Write(x + " "); Console.WriteLine(""); }}// This code contributed by shikhasingrajput |
Javascript
<script> // JavaScript Program to implement // the above approach function countXorSubarr(arr, queries, n, m) { // sum[] will contain parity // of prefix sum till index i // count[] will contain // number of 0s in sum[] let count = new Array(n + 1), sum = new Array(n + 1); count[0] = sum[0] = 0; for (let i = 1; i <= n; i++) { // Take the parity of current sum sum[i] = (sum[i - 1] + arr[i - 1]) % 2; count[i] = count[i - 1]; // If current parity is even, // increase the count if (sum[i] % 2 == 0) count[i]++; } // Array to hold the answer of 'm' queries let ans = []; // Iterate through queries and use handshake // lemma to count even sum subarrays // ( Note that an even sum can // be formed by two even or two odd ) for (let qu of queries) { let L = qu[0], R = qu[1]; // Find count of even and // odd sums in range [L, R] let even = count[R] - count[L - 1]; let odd = (R - L + 1) - even; // If prefix sum at L-1 is odd, // then we need to swap // our counts of odd and even if (sum[L - 1] == 1) { temp = even even = odd odd = temp } // Taking no element is also // considered an even sum // so even will be increased by 1 // (This is the condition when // a prefix of even sum is taken) even++; // Find number of ways to // select two even's or two odd's let subCount = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2; ans.push(subCount); } return ans; } // Driver code let n = 5; let arr = [1, 2, 9, 8, 7]; let m = 2; let queries = [[1, 5], [3, 4]]; // Function call and print answer let ans = countXorSubarr(arr, queries, n, m); for (let x of ans) document.write(x + " "); // This code is contributed by Potta Lokesh </script> |
Output
6 1
Time Complexity: O(N+M)
Auxiliary Space: O(N+M)
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!
