algoadvance

Leetcode 1720. Decode XORed Array

Problem Statement

A decoder has provided you with an integer array encoded of length n and an integer first. The encoded array is generated by encoding an original array arr, in such a way that:

You are required to decode the original array arr. To achieve this, an integer first is given as the initial value arr[0].

Return the original array arr.

Example

Input:

encoded = [1,2,3], first = 1

Output:

[1,0,2,1]

Clarifying Questions

  1. Q: What is the length of the encoded array? A: The length of the encoded array is n.

  2. Q: What will be the length of the original array arr? A: The length of the original array arr would be n + 1.

  3. Q: Are the values in the array positive numbers? A: The values in the arrays can be zero or positive integers.

Strategy

  1. Initialize an array arr with a size of n + 1.
  2. Set arr[0] to the given first value.
  3. Use the properties of XOR to decode the elements:
    • Since encoded[i] = arr[i] XOR arr[i + 1], and knowing that arr[i + 1] = encoded[i] XOR arr[i], we can calculate each value of arr iteratively.
  4. Iterate from 0 to n-1, calculating arr[i + 1] using the formula arr[i + 1] = encoded[i] XOR arr[i].

Code

#include <vector>
#include <iostream>

std::vector<int> decode(std::vector<int>& encoded, int first) {
    int n = encoded.size();
    std::vector<int> arr(n + 1);
    arr[0] = first;

    for (int i = 0; i < n; ++i) {
        arr[i + 1] = encoded[i] ^ arr[i];
    }
    return arr;
}

// Example to run the code
int main() {
    std::vector<int> encoded = {1, 2, 3};
    int first = 1;
    std::vector<int> decoded_array = decode(encoded, first);

    for (int num : decoded_array) {
        std::cout << num << " ";
    }

    return 0;
}

Time Complexity

The solution runs in linear time:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI