Determine whether a target array can be built from an array of ones by repeatedly replacing one element with the sum of the entire array.
You start with an array of length filled with $1$s. In one move, choose any index and replace that value with the sum of the entire current array.
Given a target array, decide whether it is possible to reach exactly that array from the initial array.
The key challenge is to reason backward from the target state efficiently, since forward simulation can grow very quickly.
Input Format
- An integer array
targetof length $n`. - Each
target[i]is a positive integer.
Output Format
- Return
trueiftargetcan be constructed from an array of ones using the operation described above. - Otherwise, return
false.
Constraints
- Use an approach that works well for large values and large array lengths.
Example 1
Input
target = [9,3,5]
Output
true
Explanation
One valid construction is [1,1,1] -> [1,1,3] -> [1,3,3] -> [9,3,3] -> [9,3,5].
Example 2
Input
target = [1,1,1,2]
Output
false
Explanation
No sequence of allowed operations can produce this array from all ones.
Show 1 more example
Example 3
Input
target = [8,5]
Output
true
Explanation
[1,1] -> [1,2] -> [3,2] -> [3,5] -> [8,5].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.