Construct Target Array With Multiple Sums
You are given an array target of n integers. From a starting array arr consisting of n 1s, you may perform the following procedure:
- Let
xbe the sum of all elements currently in your array. - Choose index
i, such that0 <= i < nand set the value ofarrat indexitox. - You may repeat this procedure as many times as needed.
Return true if it is possible to construct the target array from arr; otherwise, return false.
Example 1
Input
target = [9,3,5]Output
trueStarting from [1, 1, 1], you can update indices to form [1, 3, 1], then [1, 3, 5], then [9, 3, 5].
Example 2
Input
target = [1,1,1,2]Output
falseIt is impossible to create the target array from [1, 1, 1, 1].
Constraints
- n == target.length
- 1 <= n <= 5 * 10^4
- 1 <= target[i] <= 10^9