Given an array containing n numbers. The problem is to split the array into two subarrays such that the absolute difference of the xor values of the two subarrays is minimum.
Note: Array contains at least 2 numbers.
Examples:
Input : arr[] = {12, 6, 20, 14, 38, 6}
Output : 16
The two subarrays are:
{12, 6, 20} = 12 ^ 6 ^ 20 = 30
{14, 38, 6} = 14 ^ 38 ^ 6 = 46
Absolute difference = abs(30-46)
= 16
Input : arr[] = {10, 16, 9, 34, 7, 46, 23}
Output : 1
Naive Approach: Using two for loops find the xor values of the two subarrays sub_arr1[1..i] and sub_arr2[i+1..n] for every i = 1 to n-1. Find their absolute difference and accordingly update the minimum absolute difference.
Time Complexity: O(n2)
Efficient Approach: It is based on the following properties of the ^(xor) operator:
- a ^ 0 = a.
- a ^ a = 0.
Algorithm:
minDiffBtwXorValues(arr, n)
Declare tot_xor = 0
for i = 0 to n-1
tot_xor ^= arr[i]
Declare part_xor = 0
Declare min = Maximum Integer
for i = 0 to n-2
tot_xor ^= arr[i]
part_xor ^= arr[i]
if abs(tot_xor - part_xor) < min
min = abs(tot_xor - part_xor)
return min
Implementation:
C++
// C++ implementation to find the minimum // absolute difference of the xor values// of the two subarrays#include <bits/stdc++.h>using namespace std;// function to find the minimum absolute// difference of the xor values of the// two subarraysint minDiffBtwXorValues(int arr[], int n){ // to store the xor value of the // entire array int tot_xor = 0; for (int i = 0; i < n; i++) tot_xor ^= arr[i]; // 'part_xor' to store the xor value // of some subarray int part_xor = 0, min = INT_MAX; for (int i = 0; i < n - 1; i++) { // removing the xor value of the // subarray [0..i] form 'tot_xor', // i.e, it will contain the xor // value of the subarray [i+1..n-1] tot_xor ^= arr[i]; // calculating the xor value of the // subarray [0..i] part_xor ^= arr[i]; // if absolute difference is minimum, // then update 'min' if (abs(tot_xor - part_xor) < min) min = abs(tot_xor - part_xor); } // required minimum absolute difference return min;}// Driver program to test aboveint main(){ int arr[] = { 12, 6, 20, 14, 38, 6 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Minimum Absolute Difference = " << minDiffBtwXorValues(arr, n); return 0;} |
Java
// Java implementation to// find the minimum // absolute difference// of the xor values// of the two subarraysimport java.util.*;import java.lang.*;public class GfG{ // function to find // the minimum absolute // difference of the // xor values of the // two subarrays public static int minDiffBtwXorValues(int arr[], int n) { // to store the xor value of the // entire array int tot_xor = 0; for (int i = 0; i < n; i++) tot_xor ^= arr[i]; // 'part_xor' to store the xor value // of some subarray int part_xor = 0, min = Integer.MAX_VALUE; for (int i = 0; i < n - 1; i++) { // removing the xor value of the // subarray [0..i] form 'tot_xor', // i.e, it will contain the xor // value of the subarray [i+1..n-1] tot_xor ^= arr[i]; // calculating the xor value of the // subarray [0..i] part_xor ^= arr[i]; // if absolute difference is minimum, // then update 'min' if (Math.abs(tot_xor - part_xor) < min) min = Math.abs(tot_xor - part_xor); } // required minimum absolute difference return min; } // Driver function public static void main(String argc[]){ int arr[] = { 12, 6, 20, 14, 38, 6 }; int n = 6; System.out.println("Minimum Absolute Difference = " + minDiffBtwXorValues(arr, n)); } }// This code is contributed by Sagar Shukla |
Python
# Python implementation to find the minimum # absolute difference of the xor values# of the two subarraysimport sys# function to find the minimum absolute# difference of the xor values of the# two subarraysdef minDiffBtwXorValues(arr, n): # to store the xor value of the # entire array tot_xor = 0 for i in range(n): tot_xor ^= arr[i] # 'part_xor' to store the xor value # of some subarray part_xor = 0 min = sys.maxint for i in range(n - 1): # removing the xor value of the # subarray [0..i] form 'tot_xor', # i.e, it will contain the xor # value of the subarray [i+1..n-1] tot_xor ^= arr[i] # calculating the xor value of the # subarray [0..i] part_xor ^= arr[i] # if absolute difference is minimum, # then update 'min' if (abs(tot_xor - part_xor) < min): min = abs(tot_xor - part_xor) # required minimum absolute difference return min # Driver program to test abovearr = [ 12, 6, 20, 14, 38, 6 ]n = len(arr)print "Minimum Absolute Difference =", minDiffBtwXorValues(arr, n)# This code is contributed by Sachin Bisht |
C#
// C# implementation to// find the minimum// absolute difference// of the xor values// of the two subarraysusing System;class GFG { // function to find // the minimum absolute // difference of the // xor values of the // two subarrays public static int minDiffBtwXorValues(int[] arr, int n) { // to store the xor value of the // entire array int tot_xor = 0; for (int i = 0; i < n; i++) tot_xor ^= arr[i]; // 'part_xor' to store the xor value // of some subarray int part_xor = 0, min = int.MaxValue; for (int i = 0; i < n - 1; i++) { // removing the xor value of the // subarray [0..i] form 'tot_xor', // i.e, it will contain the xor // value of the subarray [i+1..n-1] tot_xor ^= arr[i]; // calculating the xor value of the // subarray [0..i] part_xor ^= arr[i]; // if absolute difference is minimum, // then update 'min' if (Math.Abs(tot_xor - part_xor) < min) min = Math.Abs(tot_xor - part_xor); } // required minimum absolute difference return min; } // Driver function public static void Main() { int[] arr = { 12, 6, 20, 14, 38, 6 }; int n = 6; Console.WriteLine("Minimum Absolute Difference = " + minDiffBtwXorValues(arr, n)); }}// This code is contributed by Sam007 |
PHP
<?php// PHP implementation to find the minimum // absolute difference of the xor values// of the two subarrays// function to find the minimum absolute// difference of the xor values of the// two subarraysfunction minDiffBtwXorValues($arr, $n){ // to store the xor value // of the entire array $tot_xor = 0; for ($i = 0; $i < $n; $i++) $tot_xor ^= $arr[$i]; // 'part_xor' to store the // xor value of some subarray $part_xor = 0; $min = PHP_INT_MAX; for ( $i = 0; $i < $n - 1; $i++) { // removing the xor value of the // subarray [0..i] form 'tot_xor', // i.e, it will contain the xor // value of the subarray [i+1..n-1] $tot_xor ^= $arr[$i]; // calculating the xor value // of the subarray [0..i] $part_xor ^= $arr[$i]; // if absolute difference is // minimum, then update 'min' if (abs($tot_xor - $part_xor) < $min) $min = abs($tot_xor - $part_xor); } // required minimum // absolute difference return $min;} // Driver Code $arr = array(12, 6, 20, 14, 38, 6); $n = count($arr); echo "Minimum Absolute Difference = " , minDiffBtwXorValues($arr, $n); // This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript implementation to find the// minimum absolute difference of the xor// values of the two subarrays// Function to find the minimum absolute// difference of the xor values of the// two subarraysfunction minDiffBtwXorValues(arr, n){ // To store the xor value of the // entire array let tot_xor = 0; for(let i = 0; i < n; i++) tot_xor ^= arr[i]; // 'part_xor' to store the xor value // of some subarray let part_xor = 0, min = Number.MAX_VALUE; for(let i = 0; i < n - 1; i++) { // Removing the xor value of the // subarray [0..i] form 'tot_xor', // i.e, it will contain the xor // value of the subarray [i+1..n-1] tot_xor ^= arr[i]; // Calculating the xor value of the // subarray [0..i] part_xor ^= arr[i]; // If absolute difference is minimum, // then update 'min' if (Math.abs(tot_xor - part_xor) < min) min = Math.abs(tot_xor - part_xor); } // Required minimum absolute difference return min;}// Driver codelet arr = [ 12, 6, 20, 14, 38, 6 ];let n = arr.length;document.write("Minimum Absolute Difference = " + minDiffBtwXorValues(arr, n)); // This code is contributed by subham348</script> |
Output
Minimum Absolute Difference = 16
Time Complexity: O(n)
Auxiliary Space : O(1)
If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.uk or mail your article to review-team@neveropen.co.uk. See your article appearing on the neveropen main page and help other Geeks.
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!
