You are given an array target of n integers. From a starting array arr consisting of n 1's, you may perform the following procedure :
x be the sum of all elements currently in your array.i, such that 0 <= i < n and set the value of arr at index i to x.Return true if it is possible to construct the target array from arr, otherwise, return false.
Example 1:
Input: target = [9,3,5] Output: true Explanation: Start with arr = [1, 1, 1] [1, 1, 1], sum = 3 choose index 1 [1, 3, 1], sum = 5 choose index 2 [1, 3, 5], sum = 9 choose index 0 [9, 3, 5] Done
Example 2:
Input: target = [1,1,1,2] Output: false Explanation: Impossible to create target array from [1,1,1,1].
Example 3:
Input: target = [8,5] Output: true
Constraints:
n == target.length1 <= n <= 5 * 1041 <= target[i] <= 109This approach uses a max-heap (priority queue) to efficiently track and operate on the largest element. The primary idea is to reverse the operation: starting from the target array, every large element in the target can be seen as the result of adding all smaller elements in the array to one of the array's elements during the last operation. By repeatedly transforming the largest element in this manner, we can verify if it is possible to reach the initial array of ones.
This C solution utilizes a sorting approach to repeatedly operate on the largest element in the array. Given the target array, it first computes the sum of the array and sorts it to keep track of the largest element. The largest element is reduced by subtracting the rest of the sum in a manner that the new largest element would be a remainder from division by rest of the array sum, thus reversing the process of the original operation. This is continued until either the array is reduced to all ones or an impossible state is reached.
C++
Java
Python
C#
JavaScript
The time complexity is O(n log n * log maxValue) due to sorting and heap operations, where n is the number of elements and maxValue is the maximum integer in the target. The space complexity is O(1) since we are sorting and using in-place operations optimistically.
This approach utilizes a sort and modulo method to reverse-track the process involved in constructing the target array from an array containing ones. It revolves around repeatedly reducing the maximum value to the remainder after division with the sum of other elements.
Steps include:
In this solution, once again a sorting technique is employed to control the biggest element in the target array for each operation. This allows management of the leading maximal element's transformation. By reducing the main element while checking the constraints, the algorithm either resolves the target to all ones or determines impossibility.
C++
Java
Python
C#
JavaScript
Time complexity is O(n log n * log maxValue); space complexity is O(1) when using in-place operations for sorting and arithmetic.
| Approach | Complexity |
|---|---|
| Approach 1: Max-Heap Backtracking | The time complexity is O(n log n * log maxValue) due to sorting and heap operations, where n is the number of elements and maxValue is the maximum integer in the target. The space complexity is O(1) since we are sorting and using in-place operations optimistically. |
| Approach 2: Iterative Modulo with Sorting | Time complexity is O(n log n * log maxValue); space complexity is O(1) when using in-place operations for sorting and arithmetic. |
Construct Target Array With Multiple Sums || Leetcode • Pepcoding • 5,621 views views
Watch 9 more video solutions →Practice Construct Target Array With Multiple Sums with our built-in code editor and test cases.
Practice on FleetCode