Bitwise XOR of same indexed array elements after rearranging an array to make XOR of same indexed elements of two arrays equal

0 0 11 minutes read

Given two arrays A[] and B[] consisting of N positive integers, the task is to the Bitwise XOR of same indexed array elements after rearranging the array B[] such that the Bitwise XOR of the same indexed elements of the arrays A[] becomes equal.

Examples:

Input: A[] = {1, 2, 3}, B[] = {4, 6, 7}
Output: 5
Explanation:
Below are the possible arrangements:

Rearrange the array B[] to {4, 7, 6}. Now, the Bitwise XOR of the same indexed elements are equal, i.e. 1 ^ 4 = 5, 2 ^ 7 = 5, 3 ^ 6 = 5.

After the rearrangements, required Bitwise XOR is 5.

Input: A[] = { 7, 8, 14 }, B[] = { 5, 12, 3 }
Output: 11
Explanation:
Below are the possible arrangements:

Rearrange the array B[] to {12, 3, 5}. Now, the Bitwise XOR of the same indexed elements are equal, i.e. 7 ^ 12 = 11, 8 ^ 3 = 11, 14 ^ 5 = 11.

After the rearrangements, required Bitwise XOR is 11.

Naive Approach: The given problem can be solved based on the observation that the count of rearrangements can be at most N because any element in A[] can only be paired with N other integers in B[]. So, there are N candidate values for X. Now, simply XOR all the candidates with each element in A[] and check if B[] can be arranged in that order.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
void findPossibleValues(int A[], int B[],
                        int n)
{
 
    // Sort the array B
    sort(B, B + n);
    int C[n];
 
    // Stores all the possible values
    // of the Bitwise XOR
    set<int> numbers;
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            C[j] = A[j] ^ candidate;
        }
 
        sort(C, C + n);
        bool flag = false;
 
        // Verify if the considered value
        // satisfies the condition or not
        for (int j = 0; j < n; j++)
            if (C[j] != B[j])
                flag = true;
 
        // Insert the possible Bitwise
        // XOR value
        if (!flag)
            numbers.insert(candidate);
    }
 
    // Print all the values obtained
    for (auto x : numbers) {
        cout << x << " ";
    }
}
 
// Driver Code
int main()
{
    int A[] = { 7, 8, 14 };
    int B[] = { 5, 12, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    findPossibleValues(A, B, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
static void findPossibleValues(int A[], int B[],
                        int n)
{
 
    // Sort the array B
    Arrays.sort(B);
    int []C = new int[n];
 
    // Stores all the possible values
    // of the Bitwise XOR
    HashSet<Integer> numbers = new HashSet<Integer>();
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            C[j] = A[j] ^ candidate;
        }
 
        Arrays.sort(C);
        boolean flag = false;
 
        // Verify if the considered value
        // satisfies the condition or not
        for (int j = 0; j < n; j++)
            if (C[j] != B[j])
                flag = true;
 
        // Insert the possible Bitwise
        // XOR value
        if (!flag)
            numbers.add(candidate);
    }
 
    // Print all the values obtained
    for (int x : numbers) {
        System.out.print(x+ " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 7, 8, 14 };
    int B[] = { 5, 12, 3 };
    int N = A.length;
    findPossibleValues(A, B, N);
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python program for the above approach
 
# Function to find all possible values
# of Bitwise XOR such after rearranging
# the array elements the Bitwise XOR
# value at corresponding indexes is same
def findPossibleValues(A, B, n):
   
  # Sort the array B
  B.sort();
  C = [0] * n;
 
  # Stores all the possible values
  # of the Bitwise XOR
  numbers = set();
 
  # Iterate over the range
  for i in range(n):
     
    # Possible value of K
    candidate = A[0] ^ B[i];
 
    # Array B for the considered
    # value of K
    for j in range(n):
      C[j] = A[j] ^ candidate;
     
 
    C.sort();
    flag = False;
 
    # Verify if the considered value
    # satisfies the condition or not
    for j in range(n):
        if (C[j] != B[j]):
             flag = True;
 
    # Insert the possible Bitwise
    # XOR value
    if (not flag): 
        numbers.add(candidate);
   
 
  # Print all the values obtained
  for x in numbers:
    print(x, end = " ");
   
# Driver Code
A = [7, 8, 14];
B = [5, 12, 3];
N = len(A);
findPossibleValues(A, B, N);
 
# This code is contributed by gfgking.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
static void findPossibleValues(int []A, int []B,
                        int n)
{
 
    // Sort the array B
    Array.Sort(B);
    int []C = new int[n];
 
    // Stores all the possible values
    // of the Bitwise XOR
    HashSet<int> numbers = new HashSet<int>();
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            C[j] = A[j] ^ candidate;
        }
 
        Array.Sort(C);
        bool flag = false;
 
        // Verify if the considered value
        // satisfies the condition or not
        for (int j = 0; j < n; j++)
            if (C[j] != B[j])
                flag = true;
 
        // Insert the possible Bitwise
        // XOR value
        if (!flag)
            numbers.Add(candidate);
    }
 
    // Print all the values obtained
    foreach (int x in numbers) {
        Console.Write(x+ " "); 
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = { 7, 8, 14 };
    int []B = { 5, 12, 3 };
    int N = A.Length;
    findPossibleValues(A, B, N);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program for the above approach
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
function findPossibleValues(A, B, n) {
  // Sort the array B
  B.sort((a, b) => a - b);
  let C = new Array(n);
 
  // Stores all the possible values
  // of the Bitwise XOR
  let numbers = new Set();
 
  // Iterate over the range
  for (let i = 0; i < n; i++) {
    // Possible value of K
    let candidate = A[0] ^ B[i];
 
    // Array B for the considered
    // value of K
    for (let j = 0; j < n; j++) {
      C[j] = A[j] ^ candidate;
    }
 
    C.sort((a, b) => a - b);
    let flag = false;
 
    // Verify if the considered value
    // satisfies the condition or not
    for (let j = 0; j < n; j++) if (C[j] != B[j]) flag = true;
 
    // Insert the possible Bitwise
    // XOR value
    if (!flag) numbers.add(candidate);
  }
 
  // Print all the values obtained
  for (let x of numbers) {
    document.write(x + " ");
  }
}
 
// Driver Code
let A = [7, 8, 14];
let B = [5, 12, 3];
let N = A.length;
findPossibleValues(A, B, N);
 
// This code is contributed by gfgking.
</script>

Output:

Time Complexity: O(N²*log(N))
Auxiliary Space: O(N)

Efficient Approach: The above approach can also be optimized by not sorting the array and store the bit-wise-XOR of all elements of B[], and then the Bitwise XOR with all elements in C[]. Now if the result is 0 then it means both arrays have same elements. Follow the steps below to solve the problem:

Initialize the variable, say x that stores the XOR of all the elements of the array B[].
Initialize a set, say numbers[] to store only unique numbers..
Iterate over the range [0, N) using the variable i and perform the following steps:
- Initialize the variables candidate as the XOR of A[0] and B[i] and curr_xor as x to see if it is 0 after performing the requires operations.
- Iterate over the range [0, N) using the variable j and perform the following steps:
  - Initialize the variable y as the XOR of A[j] and candidate and XOR y with curr_xor.
- If curr_xor is equal to 0, then insert the value candidate into the set numbers[].
After performing the above steps, print the set numbers[] as the answer.

Below is the implementation of the above approach.

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
void findPossibleValues(int A[], int B[],
                        int n)
{
    // Stores the XOR of the array B[]
    int x = 0;
 
    for (int i = 0; i < n; i++) {
        x = x ^ B[i];
    }
 
    // Stores all possible value of
    // Bitwise XOR
    set<int> numbers;
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
        int curr_xor = x;
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            int y = A[j] ^ candidate;
            curr_xor = curr_xor ^ y;
        }
 
        // This means all the elements
        // are equal
        if (curr_xor == 0)
            numbers.insert(candidate);
    }
 
    // Print all the possible value
    for (auto x : numbers) {
        cout << x << " ";
    }
}
 
// Driver Code
int main()
{
    int A[] = { 7, 8, 14 };
    int B[] = { 5, 12, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    findPossibleValues(A, B, N);
 
    return 0;
}

Java

// Java code for above approach
import java.util.*;
 
class GFG{
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
static void findPossibleValues(int A[], int B[],
                        int n)
{
    // Stores the XOR of the array B[]
    int x = 0;
 
    for (int i = 0; i < n; i++) {
        x = x ^ B[i];
    }
 
    // Stores all possible value of
    // Bitwise XOR
    HashSet<Integer> numbers = new HashSet<Integer>(); 
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
        int curr_xor = x;
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            int y = A[j] ^ candidate;
            curr_xor = curr_xor ^ y;
        }
 
        // This means all the elements
        // are equal
        if (curr_xor == 0)
            numbers.add(candidate);
    }
 
    // Print all the possible value
    for (int i : numbers) {
        System.out.print(i + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 7, 8, 14 };
    int B[] = { 5, 12, 3 };
    int N = A.length;
    findPossibleValues(A, B, N);
}
}
 
// This code is contributed by avijitmondal1998.

Python3

# Python 3 program for the above approach
 
# Function to find all possible values
# of Bitwise XOR such after rearranging
# the array elements the Bitwise XOR
# value at corresponding indexes is same
def findPossibleValues(A, B, n):
   
    # Stores the XOR of the array B[]
    x = 0
 
    for i in range(n):
        x = x ^ B[i]
 
    # Stores all possible value of
    # Bitwise XOR
    numbers = set()
 
    # Iterate over the range
    for i in range(n):
        # Possible value of K
        candidate = A[0] ^ B[i]
        curr_xor = x
 
        # Array B for the considered
        # value of K
        for j in range(n):
            y = A[j] ^ candidate
            curr_xor = curr_xor ^ y
 
        # This means all the elements
        # are equal
        if (curr_xor == 0):
            numbers.add(candidate)
 
    # Print all the possible value
    for x in numbers:
        print(x, end = " ")
 
# Driver Code
if __name__ == '__main__':
    A = [7, 8, 14]
    B = [5, 12, 3]
    N = len(A)
    findPossibleValues(A, B, N)
     
    # This code is contributed by ipg2016107.

C#

// C# code for above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
static void findPossibleValues(int []A, int []B,
                        int n)
{
   
    // Stores the XOR of the array []B
    int x = 0;
 
    for (int i = 0; i < n; i++) {
        x = x ^ B[i];
    }
 
    // Stores all possible value of
    // Bitwise XOR
    HashSet<int> numbers = new HashSet<int>(); 
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
        int curr_xor = x;
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            int y = A[j] ^ candidate;
            curr_xor = curr_xor ^ y;
        }
 
        // This means all the elements
        // are equal
        if (curr_xor == 0)
            numbers.Add(candidate);
    }
 
    // Print all the possible value
    foreach (int i in numbers) {
        Console.Write(i + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = { 7, 8, 14 };
    int []B = { 5, 12, 3 };
    int N = A.Length;
    findPossibleValues(A, B, N);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// javascript code for above approach
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
function findPossibleValues(A, B, n)
{
 
    // Stores the XOR of the array B
    var x = 0;
 
    for (var i = 0; i < n; i++) {
        x = x ^ B[i];
    }
 
    // Stores all possible value of
    // Bitwise XOR
    var numbers = new Set(); 
 
    // Iterate over the range
    for (var i = 0; i < n; i++) {
 
        // Possible value of K
        var candidate = A[0] ^ B[i];
        var curr_xor = x;
 
        // Array B for the considered
        // value of K
        for (var j = 0; j < n; j++) {
            var y = A[j] ^ candidate;
            curr_xor = curr_xor ^ y;
        }
 
        // This means all the elements
        // are equal
        if (curr_xor == 0)
            numbers.add(candidate);
    }
 
    // Print all the possible value
    for (var i of numbers) {
        document.write(i + " ");
    }
}
 
// Driver Code
var A = [ 7, 8, 14 ];
var B = [ 5, 12, 3 ];
var N = A.length;
findPossibleValues(A, B, N);
 
// This code is contributed by shikhasingrajput 
</script>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(N) as using set “numbers”

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 zambiatek!