Given an array arr[] of length N, the task is to check if we can make all elements of the array equal by taking two adjacent elements, removing them, and placing their bitwise XOR in their place until only 2 elements remain. If it’s possible, return “YES”, otherwise “NO”.
Examples:
Input: N = 3, arr[] = {0, 2, 2}
Output: YES
Explanation: we can remove the first 2 elements, 0 and 2, and replace them by 0⊕2=2(here ⊕ is the xor operator). The array will be [2, 2], so all the elements are equal.Input: N = 4, arr[] = {2, 3, 1, 10}
Output: NO
Explanation: There’s no way to make all elements equal by performing described operationInput: N = 5, arr[]={3, 3, 3, 2, 2}
Output: YES
Explanation: As we remove 3 and 2 and replace them with 3⊕2=1 and then remove 1 and 2 and replace them by 1⊕2=3, So the array will be [3, 3, 3], Hence all the elements of array becomes equal
Approach: Follow the below approach for understanding the solution.
- The Solution to this problem is to check if it’s possible to divide an array of numbers into two subsets such that the sum of elements in each subset is equal, using the XOR operation.
- The XOR operation has the property that the XOR of two equal numbers is 0. This means that if the sum of elements in one subset is equal to the sum of elements in another subset, the XOR of all elements in the first subset will be equal to the XOR of all elements in the second subset.
- The XOR operation is performed on all elements of the array to get the result stored in a variable say “xorTot“. The value of “xorTot” represents the XOR of all elements in the array. Next, For each element in the array, it performs an XOR operation with the previous result stored in a variable say “preXor“, The updated result after the XOR operation is stored back in “preXor”.
- If at any point “preXor” becomes equal to “xorTot“, it means that a subset of elements with equal sum has been found, and their XOR is equal to the XOR of all elements in the array. We initialize a count variable say “count” and whenever “preXor” becomes equal to “xorTot”, we increment our count.
- Therefore, if the value of “count” is greater than 1, it means that there are at least two subsets with an equal sum, and the array can be divided into two subsets with equal sum using the XOR operation.
Here is a step-by-step explanation of the implementation:
- Initialize variables: xorTot which will store the XOR of all elements in the array, preXor which will store the XOR of elements from the start of the array until certain index i, and count which will store the number of times the XOR of elements from the start of the array until index i is equal to xorTot.
- Loop through the array, XORing each element with xorTot to find the XOR of all elements in the array.
- Loop through the array again, XORing each element with preXor. If preXor becomes equal to xorTot, it means that the XOR of elements from the start of the array until the current index i is equal to xorTot. In this case, preXor is reset to 0 and the next index is a new start, and the count is incremented. Now check for the remaining indices
- Check if the count is greater than 1 or if xorTot is equal to 0. If either of these conditions is true, then it’s possible to split the array into two non-empty parts such that the XOR of elements in each part is equal. So, the output is “YES”. If neither of these conditions is true, then the output is “NO”.
Below is the Implementation in C++:
C++
// C++ code to implement the approach.#include <bits/stdc++.h>using namespace std;void solve(int arr[], int n){ int xorTot = 0, preXor = 0, count = 0; // XOR of all elements of array for (int i = 0; i < n; i++) { xorTot = xorTot ^ arr[i]; } for (int i = 0; i < n; i++) { preXor = preXor ^ arr[i]; // Moment certain elements of the // array become equal to xorTot. if (preXor == xorTot) preXor = 0, count++; } if (count > 1 || xorTot == 0) cout << "YES" << endl; else cout << "NO" << endl;}// Driver codeint main(){ // TestCase 1 int arr[] = { 3, 3, 3, 2, 2 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call solve(arr, n); return 0;} |
Java
import java.util.*;public class GFG { public static void solve(int[] arr, int n) { int xorTot = 0, preXor = 0, count = 0; // XOR of all elements of array for (int i = 0; i < n; i++) { xorTot = xorTot ^ arr[i]; } for (int i = 0; i < n; i++) { preXor = preXor ^ arr[i]; // Moment certain elements of the // array become equal to xorTot. if (preXor == xorTot) preXor = 0; count++; } if (count > 1 || xorTot == 0) System.out.println("YES"); else System.out.println("NO"); } // Driver code public static void main(String[] args) { // TestCase 1 int[] arr = { 3, 3, 3, 2, 2 }; int n = arr.length; // Function Call solve(arr, n); }}// this code is contributed by bhardwajji |
Python3
# Python code to implement the approach.def solve(arr, n): xorTot, preXor, count = 0, 0, 0 # XOR of all elements of array for i in range(n): xorTot ^= arr[i] for i in range(n): preXor ^= arr[i] # Moment certain elements of the # array become equal to xorTot. if preXor == xorTot: preXor, count = 0, count + 1 if count > 1 or xorTot == 0: print("YES") else: print("NO")# Driver codeif __name__ == '__main__': # TestCase 1 arr = [3, 3, 3, 2, 2] n = len(arr) # Function Call solve(arr, n) |
C#
// C# code to implement the approach.using System;public class Program{ static void Solve(int[] arr, int n) { int xorTot = 0, preXor = 0, count = 0; // XOR of all elements of array for (int i = 0; i < n; i++) { xorTot = xorTot ^ arr[i]; } for (int i = 0; i < n; i++) { preXor = preXor ^ arr[i]; // Moment certain elements of the // array become equal to xorTot. if (preXor == xorTot) preXor = 0; count++; } if (count > 1 || xorTot == 0) Console.WriteLine("YES"); else Console.WriteLine("NO"); } public static void Main() { // TestCase 1 int[] arr = { 3, 3, 3, 2, 2 }; int n = arr.Length; // Function Call Solve(arr, n); }} |
Javascript
<script> // JavaScript code to implement the approach //Function to solve the problem function solve(arr, n) { let xorTot = 0, preXor = 0, count = 0; // XOR of all elements of array for (let i = 0; i < n; i++) { xorTot = xorTot ^ arr[i]; } for (let i = 0; i < n; i++) { preXor = preXor ^ arr[i]; // Moment certain elements of the // array become equal to xorTot. if (preXor == xorTot) preXor = 0; count++; } if (count > 1 || xorTot == 0) document.write("YES"); else document.write("NO"); } //Driver code // TestCase 1 let arr = [3, 3, 3, 2, 2]; let n = arr.length; // Function Call solve(arr, n); // This code is contributed by Susobhan Akhuli</script> |
Output
YES
Time Complexity: O(N), where N is the number of elements in the array arr.
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!