Watch 10 video solutions for Construct Target Array With Multiple Sums, a hard level problem involving Array, Heap (Priority Queue). This walkthrough by Pepcoding has 5,621 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 109