Given a sequence arr[] of N-1 elements which is xor of all adjacent pairs in an array, the task is to find that original array from the arr[].
Note: It is given that the N is always odd and arr[] contains the permutation of N natural number.
Examples:
Input: arr[] = {3, 1}
Output: 1 2 3
Explanation:
The XOR of the output array will lead to the given array that is:
1 ^ 2 = 3
2 ^ 3 = 1
Input: arr[] = {7, 5, 3, 7}
Output: 3 4 1 2 5
Explanation:
The XOR of the output array will lead to the given array that is:
3 ^ 4 = 7
4 ^ 1 = 5
1 ^ 2 = 3
2 ^ 5 = 7
Approach:
- The idea is to find the XOR of all the elements of the 1 to N and the xor of the adjacent elements of the given array to find the last element of the expected array.
- As the XOR of adjacent elements will contain all the elements except the last element, then the XOR of this with all the numbers from 1 to N will give the last element of the expected permutation.
For Example:
Let's the expected array be - {a, b, c, d, e}
Then the XOR array for this array will be -
{a^b, b^c, c^d, d^e}
Now XOR of all the element from 1 to N -
xor_all => a ^ b ^ c ^ d ^ e
XOR of the adjacent elements -
xor_adjacent => ((a ^ b) ^ (c ^ d))
Now the XOR of the both the array will be the
last element of the expected permutation
=> (a ^ b ^ c ^ d ^ e) ^ ((a ^ b) ^ (c ^ d))
=> As all elements are in pair except the last element.
=> (a ^ a ^ b ^ b ^ c ^ c ^ d ^ d ^ e)
=> (0 ^ 0 ^ 0 ^ 0 ^ e)
=> e
- Now for the rest of the element, continuously, on xor of this last element we will get last second element, i.e, d.
- Repeatedly, Update the last element and finally get the first element, i.e, a.
Below is the implementation of the above approach:
C++
// C++ implementation to find the// Array from the XOR array// of the adjacent elements of array#include <bits/stdc++.h>using namespace std;// XOR of all elements from 1 to Nint xor_all_elements(int n){ switch (n & 3) { case 0: return n; case 1: return 1; case 2: return n + 1; case 3: return 0; }}// Function to find the Array// from the XOR Arrayvector<int> findArray(int xorr[], int n){ // Take a vector to store // the permutation vector<int> arr; // XOR of N natural numbers int xor_all = xor_all_elements(n); int xor_adjacent = 0; // Loop to find the XOR of // adjacent elements of the XOR Array for (int i = 0; i < n - 1; i += 2) { xor_adjacent = xor_adjacent ^ xorr[i]; } int last_element = xor_all ^ xor_adjacent; arr.push_back(last_element); // Loop to find the other // elements of the permutation for (int i = n - 2; i >= 0; i--) { // Finding the next and next elements last_element = xorr[i] ^ last_element; arr.push_back(last_element); } return arr;}// Driver Codeint main(){ vector<int> arr; int xorr[] = { 7, 5, 3, 7 }; int n = 5; arr = findArray(xorr, n); // Required Permutation for (int i = n - 1; i >= 0; i--) { cout << arr[i] << " "; }} |
Java
// Java implementation to find the// Array from the XOR array// of the adjacent elements of arrayimport java.util.*;class GFG{// XOR of all elements from 1 to Nstatic int xor_all_elements(int n){ switch (n & 3) { case 0: return n; case 1: return 1; case 2: return n + 1; } return 0;}// Function to find the Array// from the XOR Arraystatic Vector<Integer> findArray(int xorr[], int n){ // Take a vector to store // the permutation Vector<Integer> arr = new Vector<Integer>(); // XOR of N natural numbers int xor_all = xor_all_elements(n); int xor_adjacent = 0; // Loop to find the XOR of // adjacent elements of the XOR Array for (int i = 0; i < n - 1; i += 2) { xor_adjacent = xor_adjacent ^ xorr[i]; } int last_element = xor_all ^ xor_adjacent; arr.add(last_element); // Loop to find the other // elements of the permutation for (int i = n - 2; i >= 0; i--) { // Finding the next and next elements last_element = xorr[i] ^ last_element; arr.add(last_element); } return arr;}// Driver Codepublic static void main(String[] args){ Vector<Integer> arr = new Vector<Integer>(); int xorr[] = { 7, 5, 3, 7 }; int n = 5; arr = findArray(xorr, n); // Required Permutation for (int i = n - 1; i >= 0; i--) { System.out.print(arr.get(i)+ " "); }}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation to find the# Array from the XOR array# of the adjacent elements of array# XOR of all elements from 1 to Ndef xor_all_elements(n): if n & 3 == 0: return n elif n & 3 == 1: return 1 elif n & 3 == 2: return n + 1 else: return 0# Function to find the Array# from the XOR Arraydef findArray(xorr, n): # Take a vector to store # the permutation arr = [] # XOR of N natural numbers xor_all = xor_all_elements(n) xor_adjacent = 0 # Loop to find the XOR of # adjacent elements of the XOR Array for i in range(0, n - 1, 2): xor_adjacent = xor_adjacent ^ xorr[i] last_element = xor_all ^ xor_adjacent arr.append(last_element) # Loop to find the other # elements of the permutation for i in range(n - 2, -1, -1): # Finding the next and next elements last_element = xorr[i] ^ last_element arr.append(last_element) return arr# Driver Codexorr = [7, 5, 3, 7]n = 5arr = findArray(xorr, n)# Required Permutationfor i in range(n - 1, -1, -1): print(arr[i], end=" ") # This code is contributed by mohit kumar 29 |
C#
// C# implementation to find the// Array from the XOR array// of the adjacent elements of arrayusing System;using System.Collections.Generic;class GFG{ // XOR of all elements from 1 to Nstatic int xor_all_elements(int n){ switch (n & 3) { case 0: return n; case 1: return 1; case 2: return n + 1; } return 0;} // Function to find the Array// from the XOR Arraystatic List<int> findArray(int []xorr, int n){ // Take a vector to store // the permutation List<int> arr = new List<int>(); // XOR of N natural numbers int xor_all = xor_all_elements(n); int xor_adjacent = 0; // Loop to find the XOR of // adjacent elements of the XOR Array for (int i = 0; i < n - 1; i += 2) { xor_adjacent = xor_adjacent ^ xorr[i]; } int last_element = xor_all ^ xor_adjacent; arr.Add(last_element); // Loop to find the other // elements of the permutation for (int i = n - 2; i >= 0; i--) { // Finding the next and next elements last_element = xorr[i] ^ last_element; arr.Add(last_element); } return arr;} // Driver Codepublic static void Main(String[] args){ List<int> arr = new List<int>(); int []xorr = { 7, 5, 3, 7 }; int n = 5; arr = findArray(xorr, n); // Required Permutation for (int i = n - 1; i >= 0; i--) { Console.Write(arr[i]+ " "); }}}// This code contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation to find the// Array from the XOR array// of the adjacent elements of array// XOR of all elements from 1 to Nfunction xor_all_elements(n){ switch (n & 3) { case 0: return n; case 1: return 1; case 2: return n + 1; case 3: return 0; }}// Function to find the Array// from the XOR Arrayfunction findArray(xorr, n){ // Take a vector to store // the permutation let arr = []; // XOR of N natural numbers let xor_all = xor_all_elements(n); let xor_adjacent = 0; // Loop to find the XOR of // adjacent elements of the XOR Array for (let i = 0; i < n - 1; i += 2) { xor_adjacent = xor_adjacent ^ xorr[i]; } let last_element = xor_all ^ xor_adjacent; arr.push(last_element); // Loop to find the other // elements of the permutation for (let i = n - 2; i >= 0; i--) { // Finding the next and next elements last_element = xorr[i] ^ last_element; arr.push(last_element); } return arr;}// Driver Code let arr = []; let xorr = [ 7, 5, 3, 7 ]; let n = 5; arr = findArray(xorr, n); // Required Permutation for (let i = n - 1; i >= 0; i--) { document.write(arr[i] + " "); }</script> |
3 4 1 2 5
Performance Analysis:
- Time Complexity: In the above approach we iterate over the entire xor array to find the XOR of the Adjacent elements, then the complexity in the worst case will be O(N)
- Space Complexity: In the above approach there is a vector array used to store the Permutation of the numbers from 1 to N, then the space complexity will be O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] There you can find 48575 additional Info on that Topic: geeksforgeeks.org/find-the-original-array-using-xor-values-of-all-adjacent-elements/ […]
… [Trackback]
[…] Find More on that Topic: geeksforgeeks.org/find-the-original-array-using-xor-values-of-all-adjacent-elements/ […]