algoadvance

A problem titled “1720. Decode XORed Array” from Leetcode requires the following:

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, given the original array arr = [1,0,2,1], the encoded array would be encoded = [1,2,3].

You are given the encoded array. It is guaranteed that the first element of the original array is first, which is provided.

Return the original array arr.

Example

• Example 1:

    Input: encoded = [1,2,3], first = 1
    Output: [1,0,2,1]
    Explanation: 
    If arr = [1,0,2,1], then encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1, 2, 3]
  

• Example 2:

    Input: encoded = [6,2,7,3], first = 4
    Output: [4,2,0,7,4]
  

Clarifying Questions

1. Q: Can encoded array contain negative integers? A: According to the problem statement, arr consists of non-negative integers, and the XOR operation between non-negative integers will also result in non-negative integers.

2. Q: Is the length of encoded array always at least 1? A: Yes, because encoded is derived from arr which has at least two elements.

3. Q: What is the maximum size of the encoded array? A: Typically, interview problems follow constraints similar to Leetcode’s limits, i.e., up to 100,000 elements.

Strategy

To decode the XORed array, we need to reverse the encoding process. Given that: [ encoded[i] = arr[i] \oplus arr[i+1] ]

We can deduce: [ arr[i+1] = encoded[i] \oplus arr[i] ]

Starting with the first element known as first, we can compute each subsequent element of arr iteratively.

Code

def decode(encoded, first):
    # Initialize the result array with the first element
    arr = [first]
    
    # Iteratively decode each element using the XOR operation
    for i in range(len(encoded)):
        # The next element is obtained by XOR-ing the current element in arr with encoded[i]
        next_element = arr[-1] ^ encoded[i]
        arr.append(next_element)
    
    return arr

# Example usage
encoded = [1, 2, 3]
first = 1
print(decode(encoded, first))  # Output: [1, 0, 2, 1]

encoded = [6, 2, 7, 3]
first = 4
print(decode(encoded, first))  # Output: [4, 2, 0, 7, 4]

Time Complexity

• Time Complexity: ( O(n) )
  • We iterate through the encoded array once to compute the elements of arr.
• Space Complexity: ( O(n) )
  • We store the arr array which has the same length as encoded plus one, i.e., n.

This solution ensures the efficient decoding of the XORed array by leveraging the properties of XOR operation.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?