1720. Decode XORed Array

EasyBit ManipulationArray

Problem Description

In the given problem, there is an array named arr that contains n non-negative integers which we can't see because it is hidden. This arr array has been transformed into another array named encoded with a length of n - 1. This transformation uses the bitwise XOR operation: each element of encoded is the result of XORing consecutive elements in arr, i.e., encoded[i] = arr[i] XOR arr[i + 1]. The XOR operation is a bitwise operation that outputs 1 only if the input bits are different, and 0 otherwise.

The challenge is to reconstruct the original arr array given the encoded array and the first element of arr (referred to as first or arr[0]). The description assures that there is a unique solution for arr.

Intuition

The XOR operation plays a crucial role here because it has a unique property: it's reversible if we know one of the operands. Meaning, if we have a XOR b = c, we can find a by doing c XOR b, and similarly, find b by doing c XOR a. This is because performing XOR twice with the same number cancels out the operation (e.g., a XOR b XOR b is equal to a).

This property makes it possible to recover the arr array starting from the provided first element (arr[0]). The intuition behind the solution is simply to iterate through the encoded array and apply the XOR operation between the last known value of arr and the current element in encoded to find the next value of arr. In essence, given arr[i] and encoded[i], we can solve for arr[i + 1] by calculating arr[i] XOR encoded[i].

By starting with arr[0] as first and iteratively applying the XOR operation with the encoded values, we can decode the entire arr array. The solution process unfolds one element at a time, until all values in arr are revealed.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Solution Approach

The implementation utilizes a simple for loop and the append method on lists in Python. For those unfamiliar with Python, appending to a list adds a new element to the end of the list. The algorithm works as follows:

Initially, the known first element of arr (given as first) is appended to an empty list named ans.
We then iterate over each element e in the encoded array.
In each iteration, we XOR the last element of ans with e. In terms of the algorithm, if ans[-1] is the last element of the list ans, then e is XORed with ans[-1], and the result is the next element in arr, which is then appended to ans.
This method leverages the reversible property of XOR mentioned earlier: encoded[i] = arr[i] XOR arr[i + 1] implies arr[i + 1] = encoded[i] XOR arr[i]. Since arr[i] is the last known element (initially first), we can decode arr[i + 1] using the elements of encoded.
The loop continues until we have reconstructed the entire arr array.

The Solution class and its decode method, provided in the reference solution, are examples of the use of Python's object-oriented programming paradigm. The decode method encapsulates the aforementioned algorithm. There are no specific data structures besides the list used for the result, and no complex patterns -- it's a straight application of XOR to decode each subsequent number in the sequence.

Here's an explicit breakdown of the steps in the decode function:

Start by creating a result list ans with the first element first.
Iterate over the encoded array using a for loop.
In each iteration, XOR the last element of ans with the current element in encoded and append the result to ans.
Continue until all elements in encoded have been used.
The list ans is now the decoded arr array, which we return from the function.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following encoded array and first element:

encoded = [6, 1, 4]
first = 5 (which is actually arr[0])

We know that encoded[i] is derived from arr[i] XOR arr[i + 1]. So the original array arr starts with first and has n elements, with n = len(encoded) + 1.

Now we will use the given solution approach to decode the original array arr.

Step 1: Initialize the result list with `first`

ans = [5]

Step 2: XOR `first` with the first element of `encoded`

Calculate 5 XOR 6 which equals 3
Append 3 to ans
ans becomes [5, 3]

Step 3: XOR the last element of `ans` (now `3`) with the next element of `encoded`

Calculate 3 XOR 1 which equals 2
Append 2 to ans
ans becomes [5, 3, 2]

Step 4: XOR the last element of `ans` (now `2`) with the next element of `encoded`

Calculate 2 XOR 4 which equals 6
Append 6 to ans
ans becomes [5, 3, 2, 6]

At this point, we've performed an XOR operation with all elements of the encoded array, and our result list now contains all elements of the original array arr.

Final Result:

The decoded original array arr is [5, 3, 2, 6].

Using the given solution approach, we are able to reconstruct arr from encoded and first. This illustrates how the reversible property of the XOR operation can be utilized to solve this type of decoding problem iteratively.

Solution Implementation

1from typing import List
2
3class Solution:
4    def decode(self, encoded: List[int], first: int) -> List[int]:
5        # Initialize the result list with the first element
6        decoded_list = [first]
7
8        # Iterate over the encoded list and decode each element
9        for encoded_element in encoded:
10            # The next number is found by XORing the last number in the decoded list
11            # with the current encoded element
12            decoded_list.append(decoded_list[-1] ^ encoded_element)
13
14        # Return the fully decoded list
15        return decoded_list
16

1class Solution {
2  
3    /**
4     * Decodes an encoded array with the given first element value.
5     *
6     * @param encoded The array of integers to be decoded.
7     * @param first The first element of the decoded array.
8     * @return The decoded array of integers.
9     */
10    public int[] decode(int[] encoded, int first) {
11        // The length of the decoded array is one more than the length of the encoded array.
12        int n = encoded.length;
13        int[] decodedArray = new int[n + 1];
14      
15        // Setting the first element of the decoded array.
16        decodedArray[0] = first;
17      
18        // Iterating through the encoded array to decode it.
19        for (int i = 0; i < n; ++i) {
20            // The current element is obtained by XORing the previous element of the decoded
21            // array with the current element of the encoded array.
22            decodedArray[i + 1] = decodedArray[i] ^ encoded[i];
23        }
24      
25        // Returning the decoded array.
26        return decodedArray;
27    }
28}
29

1#include <vector> // Include the vector header to use std::vector
2
3class Solution {
4public:
5    // Decodes an encoded vector using the first element
6    // @param encoded: the encoded vector of integers
7    // @param first: the first element to start decoding
8    // @return the decoded vector of integers
9    std::vector<int> decode(std::vector<int>& encoded, int first) {
10        std::vector<int> decoded; // Create an empty vector to store the decoded numbers
11        decoded.push_back(first); // Add the first element to the decoded vector
12      
13        // Decode the rest of the encoded vector
14        for (int i = 0; i < encoded.size(); ++i) {
15            // The next number is found by XORing the current number with the encoded number
16            decoded.push_back(decoded[i] ^ encoded[i]);
17        }
18      
19        return decoded; // Return the fully decoded vector
20    }
21};
22

1// Import the Array type from TypeScript for type annotations
2import { Array } from "typescript";
3
4// Decode an encoded array using the first element
5// @param encoded - the encoded array of numbers
6// @param first - the first element to start decoding
7// @return the decoded array of numbers
8function decode(encoded: Array<number>, first: number): Array<number> {
9    let decoded: Array<number> = []; // Create an empty array to store the decoded numbers
10    decoded.push(first); // Add the first element to the decoded array
11
12    // Decode the rest of the encoded array
13    for (let i = 0; i < encoded.length; i++) {
14        // The next number is found by XORing the current number with the encoded number
15        decoded.push(decoded[i] ^ encoded[i]);
16    }
17
18    return decoded; // Return the fully decoded array
19}
20

Not Sure What to Study? Take the 2-min Quiz：

Which technique can we use to find the middle of a linked list?

Fast-slow pointersTwo pointers moving in opposite directionBinary searchDepth first search

I don’t know

Time and Space Complexity

Time Complexity

The given Python function decode consists of a single loop that iterates through the encoded list, which has n elements, where n is the length of the encoded list. Within the loop, there is a constant time operation which performs an XOR operation (^) and appends the result to the ans list. Therefore, since each operation in the loop takes O(1) time and the loop runs for n iterations, the overall time complexity is O(n).

Space Complexity

The space complexity of the function decode is determined by the ans list which the function populates and returns. Since the ans list will contain exactly n + 1 elements after processing an encoded list of length n, the space complexity is O(n). The space required grows linearly with the input size, making the space complexity linear as well.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1720. Decode XORed Array

Problem Description

Intuition

Solution Approach

Example Walkthrough

Step 1: Initialize the result list with first

Step 2: XOR first with the first element of encoded

Step 3: XOR the last element of ans (now 3) with the next element of encoded

Step 4: XOR the last element of ans (now 2) with the next element of encoded

Final Result:

Solution Implementation

Step 1: Initialize the result list with `first`

Step 2: XOR `first` with the first element of `encoded`

Step 3: XOR the last element of `ans` (now `3`) with the next element of `encoded`

Step 4: XOR the last element of `ans` (now `2`) with the next element of `encoded`