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
People are also reading:
- Count the number of strictly increasing subarrays in an array
- WAP to create a loading bar
- Find duplicates within a range k in an array
- WAP to print given series:1 2 4 8 16 32 64 128
- Python Array
- Find the longest subsequence formed by consecutive integers
- WAP to calculate area of a circle, a rectangle or a triangle
- Determine the index of an element that satisfies given constraints in an array
- Python Program to Find LCM
- Find minimum sum of a subarray of size k
- Python Program to Check Armstrong Number
