Given two arrays A[] and B[] consisting of N integers (N is odd), the task is to rearrange array B[] such that for each 1 ? i ? N, Bitwise XOR of A[i] and B[i] is the same. If no such rearrangement is possible, print “-1”. Otherwise, print the rearrangement.
Examples:
Input: A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1}
Output: {1, 2, 3, 4, 5}
Explanation:
Rearranging the array B[] to {1, 2, 3, 4, 5}, Bitwise XOR between every corresponding pair of array elements is same i.e., 0.Input: A[] = {14, 21, 33, 49, 53}, B[] = {54, 50, 34, 22, 14}
Output: -1
Naive Approach: The simplest approach is to generate all possible arrangements of array B[] and print that combinations of the array whose Bitwise XOR with corresponding elements is the same.
Time Complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: The idea is to use the commutative property of Bitwise XOR. Below are the steps:
- Find the Bitwise XOR of both the array elements let the value be xor_value.
- Store the frequency of element of the array B[] in a map M.
- For rearranging the array elements of B[] traverse the array B[] and do the following:
- Update the current element of this array as A[i]^xor_value.
- If the frequency of the updated current element is greater than 1 then decrement it.
- Otherwise, there is no such possible arrangement, break out of the loop, and print “-1”.
- After the above steps are completed, print the array B[] as it contains the rearranged array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to rearrange the array// B[] such that A[i] ^ B[i] is same// for each elementvector<int> rearrangeArray( vector<int>& A, vector<int>& B, int N){ // Store frequency of elements map<int, int> m; // Stores xor value int xor_value = 0; for (int i = 0; i < N; i++) { // Taking xor of all the // values of both arrays xor_value ^= A[i]; xor_value ^= B[i]; // Store frequency of B[] m[B[i]]++; } for (int i = 0; i < N; i++) { // Find the array B[] after // rearrangement B[i] = A[i] ^ xor_value; // If the updated value is // present then decrement // its frequency if (m[B[i]]) { m[B[i]]--; } // Otherwise return empty vector else return vector<int>{}; } return B;}// Utility function to rearrange the// array B[] such that A[i] ^ B[i]// is same for each elementvoid rearrangeArrayUtil( vector<int>& A, vector<int>& B, int N){ // Store rearranged array B vector<int> ans = rearrangeArray(A, B, N); // If rearrangement possible if (ans.size()) { for (auto x : ans) { cout << x << " "; } } // Otherwise return -1 else { cout << "-1"; }}// Driver Codeint main(){ // Given vector A vector<int> A = { 13, 21, 33, 49, 53 }; // Given vector B vector<int> B = { 54, 50, 34, 22, 14 }; // Size of the vector int N = (int)A.size(); // Function Call rearrangeArrayUtil(A, B, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to rearrange the array// B[] such that A[i] ^ B[i] is same// for each elementstatic ArrayList<Integer> rearrangeArray( ArrayList<Integer> A, ArrayList<Integer> B, int N){ // Store frequency of elements HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); // Stores xor value int xor_value = 0; for(int i = 0; i < N; i++) { // Taking xor of all the // values of both arrays xor_value ^= A.get(i); xor_value ^= B.get(i); // Store frequency of B[] m.put(B.get(i), m.getOrDefault(B.get(i) + 1, 0)); } for(int i = 0; i < N; i++) { // Find the array B[] after // rearrangement B.set(i, A.get(i) ^ xor_value); // If the updated value is // present then decrement // its frequency if (m.getOrDefault(B.get(i), -1) != -1) { m.put(B.get(i), m.getOrDefault(B.get(i), 0) - 1); } // Otherwise return empty vector else return (new ArrayList<Integer>()); } return B;}// Utility function to rearrange the// array B[] such that A[i] ^ B[i]// is same for each elementstatic void rearrangeArrayUtil(ArrayList<Integer> A, ArrayList<Integer> B, int N){ // Store rearranged array B ArrayList<Integer> ans = rearrangeArray(A, B, N); // If rearrangement possible if (ans.size() != 0) { for(int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i) + " "); } } // Otherwise return -1 else { System.out.println("-1"); }}// Driver Codepublic static void main(String[] args){ // Given vector A ArrayList<Integer> A = new ArrayList<Integer>( Arrays.asList(13, 21, 33, 49, 53)); // Given vector B ArrayList<Integer> B = new ArrayList<Integer>( Arrays.asList(54, 50, 34, 22, 14)); // Size of the vector int N = (int)A.size(); // Function Call rearrangeArrayUtil(A, B, N);}}// This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach# Function to rearrange the array# B[] such that A[i] ^ B[i] is same# for each elementdef rearrangeArray(A, B, N): # Store frequency of elements m = {} # Stores xor value xor_value = 0 for i in range(0, N): # Taking xor of all the # values of both arrays xor_value ^= A[i] xor_value ^= B[i] # Store frequency of B[] if B[i] in m: m[B[i]] = m[B[i]] + 1 else: m[B[i]] = 1 for i in range(0, N): # Find the array B[] after # rearrangement B[i] = A[i] ^ xor_value # If the updated value is # present then decrement # its frequency if B[i] in m: m[B[i]] = m[B[i]] - 1 # Otherwise return empty vector else: X = [] return X return B# Utility function to rearrange the# array B[] such that A[i] ^ B[i]# is same for each elementdef rearrangeArrayUtil(A, B, N): # Store rearranged array B ans = rearrangeArray(A, B, N) # If rearrangement possible if (len(ans) > 0): for x in ans: print(x, end = ' ') # Otherwise return -1 else: print("-1") # Driver Codeif __name__ == '__main__': # Given vector A A = [ 13, 21, 33, 49, 53 ] # Given vector B B = [ 54, 50, 34, 22, 14 ] # Size of the vector N = len(A) # Function Call rearrangeArrayUtil(A, B, N) # This code is contributed by akhilsaini |
C#
// C# program for the above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{// Function to rearrange the array// B[] such that A[i] ^ B[i] is same// for each elementstatic ArrayList rearrangeArray(ArrayList A, ArrayList B, int N){ // Store frequency of elements Dictionary<int, int> m = new Dictionary<int, int>(); // Stores xor value int xor_value = 0; for(int i = 0; i < N; i++) { // Taking xor of all the // values of both arrays xor_value ^= (int)A[i]; xor_value ^= (int)B[i]; // Store frequency of B[] if (!m.ContainsKey((int)B[i])) m.Add((int)B[i], 1); else m[(int)B[i]] = m[(int)B[i]] + 1; } for(int i = 0; i < N; i++) { // Find the array B[] after // rearrangement B[i] = (int)A[i] ^ xor_value; // If the updated value is // present then decrement // its frequency if (m.ContainsKey((int)B[i])) { m[(int)B[i]]--; } // Otherwise return empty vector else return (new ArrayList()); } return B;}// Utility function to rearrange the// array B[] such that A[i] ^ B[i]// is same for each elementstatic void rearrangeArrayUtil(ArrayList A, ArrayList B, int N){ // Store rearranged array B ArrayList ans = rearrangeArray(A, B, N); // If rearrangement possible if (ans.Count != 0) { for(int i = 0; i < ans.Count; i++) { Console.Write(ans[i] + " "); } } // Otherwise return -1 else { Console.WriteLine("-1"); }}// Driver Codepublic static void Main(){ // Given vector A ArrayList A = new ArrayList{ 13, 21, 33, 49, 53 }; // Given vector B ArrayList B = new ArrayList{ 54, 50, 34, 22, 14 }; // Size of the vector int N = A.Count; // Function Call rearrangeArrayUtil(A, B, N);}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program for the above approach// Function to rearrange the array// B[] such that A[i] ^ B[i] is same// for each elementfunction rearrangeArray(A, B, N) { // Store frequency of elements let m = new Map(); // Stores xor value let xor_value = 0; for (let i = 0; i < N; i++) { // Taking xor of all the // values of both arrays xor_value ^= A[i]; xor_value ^= B[i]; // Store frequency of B[] if (m.has(B[i])) { m.set(B[i], m.get(B[i]) + 1) } else { m.set(B[i], 1) } } for (let i = 0; i < N; i++) { // Find the array B[] after // rearrangement B[i] = A[i] ^ xor_value; // If the updated value is // present then decrement // its frequency if (m.has(B[i])) { m.set(B[i], m.get(B[i]) - 1) } // Otherwise return empty vector else return []; } return B;}// Utility function to rearrange the// array B[] such that A[i] ^ B[i]// is same for each elementfunction rearrangeArrayUtil(A, B, N){ // Store rearranged array B let ans = rearrangeArray(A, B, N); // If rearrangement possible if (ans.length > 0) { for (let x of ans) { document.write(x + " "); } } // Otherwise return -1 else { document.write("-1"); }}// Driver Code// Given vector Alet A = [13, 21, 33, 49, 53];// Given vector Blet B = [54, 50, 34, 22, 14];// Size of the vectorlet N = A.length;// Function CallrearrangeArrayUtil(A, B, N);// This code is contributed by _saurabh_jaiswal.</script> |
Output:
14 22 34 50 54
Time Complexity: O(N)
Auxiliary Space: O(N)
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!