Skip to content

Latest commit

 

History

History
78 lines (51 loc) · 2.59 KB

030.md

File metadata and controls

78 lines (51 loc) · 2.59 KB
Raw

2433. Find The Original Array of Prefix Xor

Difficulty: 🟡 Medium

You are given an integer array pref of size n. Find and return the array arr of size n that satisfies:

  • pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].

Note that ^ denotes the bitwise-xor operation.

It can be proven that the answer is unique.

Examples:

Example 1:

Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation: From the array [5,7,2,3,2] we have the following:
- pref[0] = 5.
- pref[1] = 5 ^ 7 = 2.
- pref[2] = 5 ^ 7 ^ 2 = 0.
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3.
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1.

Example 2:

Input: pref = [13]
Output: [13]
Explanation: We have pref[0] = arr[0] = 13.

Constraints:

  • 1 <= pref.length <= 105
  • 0 <= pref[i] <= 106

Solutions

O(n) solution in Python3

class Solution:
    def findArray(self, pref: List[int]) -> List[int]:
        answer= [pref[0]]
        for i in range(len(pref)-1):
            answer.append(pref[i]^pref[i+1])

        return answer

The given solution constructs the array arr based on the given pref array by performing the bitwise XOR operation between adjacent elements.

The algorithm works as follows:

  1. Initialize an empty array answer with the first element of pref as the first element of answer.
  2. Iterate through the range from 0 to the length of pref minus 1:
    • Calculate the XOR of the current element in pref and the next element in pref.
    • Append the result of the XOR operation to the answer array.
  3. Return the answer array, which represents the array arr that satisfies the given condition.

The algorithm constructs the answer array by performing the bitwise XOR operation between adjacent elements of the pref array.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the size of the pref array. The algorithm iterates through the pref array once and performs a constant-time XOR operation at each iteration.

The space complexity of the algorithm is O(n) as it creates a new array, answer, to store the elements of arr.

Summary

The given solution constructs the array arr based on the given pref array by performing the bitwise XOR operation between adjacent elements. 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.