Given an array arr[] of size N, the task is to count the number of subarrays from the given array whose Bitwise XOR is even.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: 4
Explanation: The subarrays having even Bitwise XOR are {{2}, {4}, {1, 2, 3}, {1, 2, 3, 4}}.Input: arr[] = {2, 4, 6}
Output: 6
Explanation: The subarrays having even Bitwise XOR are {{2}, {4}, {6}, {2, 4}, {4, 6}, {2, 4, 6}}.
Naive Approach: The simplest approach to solve this problem is to generate all possible subarrays and check for every subarray, whether Bitwise XOR of all its elements are even or not. If found to be even, then increase the count. Finally, print the count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// subarrays having even Bitwise XORvoid evenXorSubarray(int arr[], int n){ // Store the required result int ans = 0; // Generate subarrays with // arr[i] as the first element for (int i = 0; i < n; i++) { // Store XOR of current subarray int XOR = 0; // Generate subarrays with // arr[j] as the last element for (int j = i; j < n; j++) { // Calculate Bitwise XOR // of the current subarray XOR = XOR ^ arr[j]; // If XOR is even, // increase ans by 1 if ((XOR & 1) == 0) ans++; } } // Print the result cout << ans;}// Driver Codeint main(){ // Given array int arr[] = { 1, 2, 3, 4 }; // Stores the size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function Call evenXorSubarray(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to count the number of // subarrays having even Bitwise XOR static void evenXorSubarray(int arr[], int n) { // Store the required result int ans = 0; // Generate subarrays with // arr[i] as the first element for (int i = 0; i < n; i++) { // Store XOR of current subarray int XOR = 0; // Generate subarrays with // arr[j] as the last element for (int j = i; j < n; j++) { // Calculate Bitwise XOR // of the current subarray XOR = XOR ^ arr[j]; // If XOR is even, // increase ans by 1 if ((XOR & 1) == 0) ans++; } } // Print the result System.out.println(ans); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 1, 2, 3, 4 }; // Stores the size of the array int N = arr.length; evenXorSubarray(arr, N); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approach# Function to count the number of# subarrays having even Bitwise XORdef evenXorSubarray(arr, n): # Store the required result ans = 0 # Generate subarrays with # arr[i] as the first element for i in range(n): # Store XOR of current subarray XOR = 0 # Generate subarrays with # arr[j] as the last element for j in range(i, n): # Calculate Bitwise XOR # of the current subarray XOR = XOR ^ arr[j] # If XOR is even, # increase ans by 1 if ((XOR & 1) == 0): ans += 1 # Print the result print (ans)# Driver Codeif __name__ == '__main__': # Given array arr = [1, 2, 3, 4] # Stores the size of the array N = len(arr) # Function Call evenXorSubarray(arr, N)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{ // Function to count the number of // subarrays having even Bitwise XOR static void evenXorSubarray(int[] arr, int n) { // Store the required result int ans = 0; // Generate subarrays with // arr[i] as the first element for (int i = 0; i < n; i++) { // Store XOR of current subarray int XOR = 0; // Generate subarrays with // arr[j] as the last element for (int j = i; j < n; j++) { // Calculate Bitwise XOR // of the current subarray XOR = XOR ^ arr[j]; // If XOR is even, // increase ans by 1 if ((XOR & 1) == 0) ans++; } } // Print the result Console.WriteLine(ans); } // Driver Code public static void Main() { // Given array int[] arr = { 1, 2, 3, 4 }; // Stores the size of the array int N = arr.Length; evenXorSubarray(arr, N); }}// This code is contributed by souravghosh0416. |
Javascript
<script>// Javascript program for the above approach// Function to count the number of// subarrays having even Bitwise XORfunction evenXorSubarray(arr, n){ // Store the required result let ans = 0; // Generate subarrays with // arr[i] as the first element for (let i = 0; i < n; i++) { // Store XOR of current subarray let XOR = 0; // Generate subarrays with // arr[j] as the last element for (let j = i; j < n; j++) { // Calculate Bitwise XOR // of the current subarray XOR = XOR ^ arr[j]; // If XOR is even, // increase ans by 1 if ((XOR & 1) == 0) ans++; } } // Print the result document.write(ans);}// Driver Code// Given arraylet arr = [ 1, 2, 3, 4 ];// Stores the size of the arraylet N = arr.length;// Function CallevenXorSubarray(arr, N);</script> |
Output:
4
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on following observations:
Bitwise XOR of all elements in the range of indices [i + 1, j] be A.
Bitwise XOR of all elements in the range of indices [0, i] be B.
Bitwise XOR of all elements in the range of indices [0, j] be C.
By performing B ^ C, the common elements from the two ranges cancel out, resulting in XOR of all elements from the range [i + 1, j].
Therefore, the idea is to update the number of subarrays starting from index 0, having even and odd XOR values while traversing the array and updating the count accordingly. Follow the steps below to solve the problem:
- Initialize two variables, say ans and XOR, to store the required count of subarrays and store XOR values of subarrays respectively.
- Initialize an array, say freq[] of size 2, where freq[0] denotes the number of subarrays having even XOR value, and freq[1] denotes the number of subarrays having odd XOR values, starting from the index 0.
- Traverse the array, arr[] using a variable, say i, and for each array element:
- Update the value of XOR to XOR ^ arr[i].
- If XOR is even, then increase the value of ans by 1 + freq[0].
- Increment freq[0] by 1, because when subarray {arr[0], i] is XORed with other subarrays having even xor value then it would result in an even XOR value. Also, 1 is added to consider the entire subarray[0, i].
- Similarly, if XOR is odd, increment ans by freq[1] and increment freq[1] by 1.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count subarrays// having even Bitwise XORvoid evenXorSubarray(int arr[], int n){ // Store the required result int ans = 0; // Stores count of subarrays // with even and odd XOR values int freq[] = { 0, 0 }; // Stores Bitwise XOR of // current subarray int XOR = 0; // Traverse the array for (int i = 0; i < n; i++) { // Update current Xor XOR = XOR ^ arr[i]; // If XOR is even if (XOR % 2 == 0) { // Update ans ans += freq[0] + 1; // Increment count of // subarrays with even XOR freq[0]++; } else { // Otherwise, increment count // of subarrays with odd XOR ans += freq[1]; freq[1]++; } } // Print the result cout << ans;}// Driver Codeint main(){ // Given array int arr[] = { 1, 2, 3, 4 }; // Stores the size of the array int N = sizeof(arr) / sizeof(arr[0]); evenXorSubarray(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to count subarrays // having even Bitwise XOR static void evenXorSubarray(int arr[], int n) { // Store the required result int ans = 0; // Stores count of subarrays // with even and odd XOR values int freq[] = { 0, 0 }; // Stores Bitwise XOR of // current subarray int XOR = 0; // Traverse the array for (int i = 0; i < n; i++) { // Update current Xor XOR = XOR ^ arr[i]; // If XOR is even if (XOR % 2 == 0) { // Update ans ans += freq[0] + 1; // Increment count of // subarrays with even XOR freq[0]++; } else { // Otherwise, increment count // of subarrays with odd XOR ans += freq[1]; freq[1]++; } } // Print the result System.out.println(ans); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 1, 2, 3, 4 }; // Stores the size of the array int N = arr.length; evenXorSubarray(arr, N); }} |
Python3
# Python3 program for the above approach# Function to count subarrays# having even Bitwise XORdef evenXorSubarray(arr, n): # Store the required result ans = 0 # Stores count of subarrays # with even and odd XOR values freq = [0] * n # Stores Bitwise XOR of # current subarray XOR = 0 # Traverse the array for i in range(n): # Update current Xor XOR = XOR ^ arr[i] # If XOR is even if (XOR % 2 == 0): # Update ans ans += freq[0] + 1 # Increment count of # subarrays with even XOR freq[0] += 1 else: # Otherwise, increment count # of subarrays with odd XOR ans += freq[1] freq[1] += 1 # Print the result print(ans)# Driver Code# Given arrayarr = [ 1, 2, 3, 4 ]# Stores the size of the arrayN = len(arr) evenXorSubarray(arr, N)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG { // Function to count subarrays // having even Bitwise XOR static void evenXorSubarray(int[] arr, int n) { // Store the required result int ans = 0; // Stores count of subarrays // with even and odd XOR values int[] freq = { 0, 0 }; // Stores Bitwise XOR of // current subarray int XOR = 0; // Traverse the array for (int i = 0; i < n; i++) { // Update current Xor XOR = XOR ^ arr[i]; // If XOR is even if (XOR % 2 == 0) { // Update ans ans += freq[0] + 1; // Increment count of // subarrays with even XOR freq[0]++; } else { // Otherwise, increment count // of subarrays with odd XOR ans += freq[1]; freq[1]++; } } // Print the result Console.WriteLine(ans); } // Driver Code public static void Main(String[] args) { // Given array int[] arr = { 1, 2, 3, 4 }; // Stores the size of the array int N = arr.Length; evenXorSubarray(arr, N); }}// This code is contributed by susmitakundugoaldanga. |
Javascript
<script>// Javascript program for the above approach// Function to count subarrays// having even Bitwise XORfunction evenXorSubarray(arr, n){ // Store the required result let ans = 0; // Stores count of subarrays // with even and odd XOR values let freq = [ 0, 0 ]; // Stores Bitwise XOR of // current subarray let XOR = 0; // Traverse the array for (let i = 0; i < n; i++) { // Update current Xor XOR = XOR ^ arr[i]; // If XOR is even if (XOR % 2 == 0) { // Update ans ans += freq[0] + 1; // Increment count of // subarrays with even XOR freq[0]++; } else { // Otherwise, increment count // of subarrays with odd XOR ans += freq[1]; freq[1]++; } } // Print the result document.write(ans);}// Driver Code // Given array let arr = [ 1, 2, 3, 4 ]; // Stores the size of the array let N = arr.length; evenXorSubarray(arr, N); </script> |
Output:
4
Time Complexity: O(N)
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!
