algoadvance

Leetcode 1720. Decode XORed Array

Problem Statement

You are given the encoded array encoded of length n and an integer first. You need to find the original array arr that was used to generate the encoded array.

The encoded array is created using the XOR operation as follows:

• encoded[i] = arr[i] ^ arr[i + 1] for i >= 0.

Given:

• An integer first.
• An integer array encoded of length n (where n is at least 1).

You need to return the original array arr of length n + 1 where arr[0] = first.

Clarifying Questions

1. Is the length of the encoded array guaranteed to be at least 1?
   • Yes, it’s guaranteed to be at least 1.
2. Can the encoded array contain negative numbers?
   • No, it contains non-negative integers.
3. Is the first integer guaranteed to be within a specific range?
   • first can be any non-negative integer within the range of typical 32-bit integers.

Strategy

To decode the encoded array:

1. Initialize an array arr where the length is n + 1.
2. Set the first element of arr as first.
3. Iterate through the encoded array, use the property of XOR to compute the original value:
   • XOR has a property that a ^ b = c implies a = c ^ b.
   • Therefore, arr[i] = encoded[i-1] ^ arr[i-1].

Code

public class Solution {
    public int[] decode(int[] encoded, int first) {
        int n = encoded.length;
        int[] arr = new int[n + 1];
        arr[0] = first;
        
        for (int i = 0; i < n; i++) {
            arr[i + 1] = encoded[i] ^ arr[i];
        }
        
        return arr;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the encoded array. This is because we iterate through each element of the encoded array exactly once.
• Space Complexity: O(n), for storing the arr array of size n + 1.

This solution efficiently decodes the XORed array using a straightforward iteration and XOR operations.

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

• 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?