Decode an array constructed from another array

Posted in

Decode an array constructed from another array
vinaykhatri

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

    People are also reading:

    Leave a Comment on this Post

    0 Comments