Leetcode 2433: Find The Original Array of Prefix Xor
You are given an integer array
pref of size n. Your task is to find and return an array arr of size n that satisfies the following condition: each element pref[i] equals the XOR of all elements from arr[0] to arr[i]. In other words, pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i] where ^ denotes the bitwise XOR operation. It is guaranteed that there is a unique solution.Problem
Approach
Steps
Complexity
Input: You are given a single array `pref` of integers.
Example: pref = [3, 1, 2, 6]
Constraints:
• 1 <= pref.length <= 10^5
• 0 <= pref[i] <= 10^6
Output: Return an array `arr` that satisfies the condition: `pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]`.
Example: Output: [3, 2, 0, 6]
Constraints:
• The answer will always be unique.
Goal: We need to find an array `arr` such that the cumulative XOR of its elements matches the corresponding values in `pref`.
Steps:
• 1. Initialize an empty array `arr` of the same size as `pref`.
• 2. Set `arr[0]` equal to `pref[0]` since the first element is directly equal.
• 3. For each subsequent index `i`, calculate `arr[i]` as `pref[i] ^ pref[i-1]`. This is because `pref[i]` represents the cumulative XOR of `arr[0]` to `arr[i]`, and `pref[i-1]` represents the cumulative XOR of `arr[0]` to `arr[i-1]`, so XORing them will give the value of `arr[i]`.
• 4. Return the array `arr`.
Goal: Consider the following constraints while designing the solution.
Steps:
• The array `pref` has at least one element.
• The XOR operation is associative and commutative.
Assumptions:
• The input array `pref` is valid and contains at least one element.
• Each element of `pref` is non-negative and less than or equal to 10^6.
• Input: pref = [3, 1, 2, 6]
• Explanation: To solve this, we find `arr` such that each `pref[i]` is the cumulative XOR of `arr[0]` to `arr[i]`. From `pref`, we can derive `arr` as follows: `arr[0] = 3`, `arr[1] = 3 ^ 1 = 2`, `arr[2] = 2 ^ 2 = 0`, `arr[3] = 0 ^ 6 = 6`. Thus, the result is `[3, 2, 0, 6]`.
• Input: pref = [10]
• Explanation: In this case, the array `arr` will be equal to `pref[0]` because there is only one element. Thus, the result is `[10]`.
Approach: The solution is based on the property of the XOR operation. By using the cumulative XOR relationship, we can deduce each element of the array `arr` from the `pref` array.
Observations:
• The problem involves working with the XOR operation, which is associative and commutative.
• We can solve the problem iteratively by using the property of XOR to derive each element of `arr` from the prefix XOR values in `pref`.
Steps:
• 1. Create an array `arr` of the same length as `pref`.
• 2. Set `arr[0]` equal to `pref[0]`.
• 3. For each subsequent element `i`, calculate `arr[i] = pref[i] ^ pref[i-1]`.
• 4. Return the `arr` array.
Empty Inputs:
• There are no empty inputs as `pref` always has at least one element.
Large Inputs:
• Ensure that the solution can handle arrays of size up to 100,000 efficiently.
Special Values:
• Handle cases where `pref` has a single element, as `arr` will just be equal to `pref`.
Constraints:
• Ensure the solution is efficient and runs in O(n) time complexity.
vector<int> findArray(vector<int>& pref) {
vector<int> res(pref.size());
res[0] = pref[0];
for(int i = 1; i < pref.size(); i++)
res[i] = pref[i] ^ pref[i - 1];
return res;
}
1 : Function Definition
vector<int> findArray(vector<int>& pref) {
Function definition for 'findArray', which takes a reference to a vector of integers 'pref' and returns a vector of integers.
2 : Vector Initialization
vector<int> res(pref.size());
A new vector 'res' is initialized with the same size as 'pref', which will store the reconstructed array.
3 : Initial Assignment
res[0] = pref[0];
The first element of the result vector 'res' is set to the first element of the 'pref' vector, since it's directly copied.
4 : Loop
for(int i = 1; i < pref.size(); i++)
A for loop is initiated to iterate through the 'pref' vector starting from the second element.
5 : XOR Operation
res[i] = pref[i] ^ pref[i - 1];
For each iteration, the XOR operation is performed between the current element and the previous element of 'pref' to reconstruct the original array.
6 : Return Result
return res;
Return the reconstructed array 'res' as the result.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the `pref` array. We iterate through `pref` once, and each operation inside the loop takes constant time.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n), as we need to store the result array `arr`.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus