Skip to content

Latest commit

 

History

History
72 lines (48 loc) · 2.69 KB

039.md

File metadata and controls

72 lines (48 loc) · 2.69 KB

1720. Decode XORed Array

Difficulty: 🟢 Easy

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 = [1,0,2,1], then encoded = [1,2,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.

Examples:

Example 1:

Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]
Explanation: If arr = [1,0,2,1], then first = 1 and 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]

Constraints:

  • 2 <= n <= 104
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 105
  • 0 <= first <= 105

Solutions

O(n) solution in Python3

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        result = [first]
        for num in encoded:
            first ^= num
            result.append(first)
        return result

The given solution decodes the encoded array into the original array using XOR operations. It iterates through the encoded array and applies XOR operations to reconstruct the original array.

The algorithm works as follows:

  1. Initialize a result array with the first element, first, of the original array.
  2. Iterate through the encoded array:
    • Apply XOR operation between the current element, num, in the encoded array and the previous element in the result array, first. Update first with the XOR result.
    • Append the updated first to the result array.
  3. Return the result array, which represents the original array.

By iteratively applying XOR operations between consecutive elements, the algorithm reconstructs the original array.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the length of the encoded array. The algorithm iterates through the encoded array once and performs constant-time operations at each iteration.

The space complexity of the algorithm is O(n) as it uses additional space to store the result array, which has a length of n.

Summary

The given solution decodes the encoded array into the original array using XOR operations. It has a time complexity of O(n) and a space complexity of O(n), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.