Decode an array constructed from another array

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