# Decode an array constructed from another array

Posted in

Vinay Khatri
Last updated on July 13, 2024

## Problem

There is a hidden integer array arr that consists of ``` n ``` non-negative integers. It was encoded into another integer array encoded of length ``` n - 1 ``` , such that ``` encoded[i] = arr [i] XOR arr [i + 1] ``` .

For example, if ``` arr = [4, 2, 0, 7, 4 ``` ``` ] ``` then ``` encoded = [6, 2, 7, 3] ``` .You are given the encoded array. You are also given an integer. First, that is the first element of arr, i.e. ``` arr [0] ``` . Return the original array ``` arr ``` . It can be proved that the answer exists and is unique.

## Approach

We can use the property of XORing here. If, for some integers a , b, and c , ``` a ^ b = c ``` then ``` b = a ^ c ``` . Using this approach, since the first element of the original array is given, the next element of the decoded array is ``` decoded[0] ^ encoded[0] ``` .

We can perform a similar operation on the rest of the elements and decode the entire array. The time complexity of this approach is O(N).

### C++ Programming

```#include<bits/stdc++.h>
using namespace std;

//function to return decoded array
vector<int> decode(vector<int>& encoded, int first) {
vector<int>decoded;
int n = encoded.size();

decoded.push_back(first);    //first element is given
for(int i=0;i<n;i++){
decoded.push_back(decoded[i]^encoded[i]);  //find next element
}
return decoded;
}
int main(){
vector<int>encoded{6, 2, 7, 3};
int first = 4;
vector<int>ans = decode(encoded, first);
for(auto itr: ans) cout<<itr<<" ";
}```

Output

`4 2 0 7 4`

### Python Programming

```#function to decode array
def decode(a, first):
a=[]
a.append(first)   #first element is given to us
x=first
for i in encoded:
x^=i       #find next element
a.append(x)
return a
encoded = [6, 2, 7, 3]
first = 4
print(decode(encoded, first))```

Output

`[4, 2, 0, 7, 4]`

### C Programming

```#include<stdio.h>

//function to return decoded array
void decode(int encoded[], int first) {
int decoded[5];

decoded[0] = first;    //first element is given
for(int i=0;i<4;i++){
decoded[i+1] = decoded[i]^encoded[i];  //find next element
}
for(int i=0;i<5;i++){
printf("%d ", decoded[i]);
}
}
int main(){
int encoded[4] = {6, 2, 7, 3};
int first = 4;
decode(encoded, first);
}```

Output

`4 2 0 7 4`