Construct Target Array With Multiple Sums — Hard Problem & Solution

Problem statement

Start from an array of n ones. In one step you may compute the sum s of the whole array, pick any index i, and set arr[i] = s.

Return true if target can be reached by some sequence of such steps.

Example 1

Input: target = [9,3,5]
Output: true
Explanation: `[1,1,1] → [1,1,3] → [1,3,3]`… working backwards from `[9,3,5]` reaches all ones.

Example 2

Input: target = [1,1,1,2]
Output: false
Explanation: The 2 would have had to be the sum of the others, which is 3.

Example 3

Input: target = [8,5]
Output: true

Constraints

• n == target.length
• 1 <= n <= 5 * 10^4
• 1 <= target[i] <= 10^9

How to solve Construct Target Array With Multiple Sums

Reverse the process. The largest element is always the one written most recently, so replace it with largest mod rest, where rest is the total of the others, and repeat until everything is 1.

Approach

1. Keep the values in a max-heap and track the running total.
2. While the top exceeds 1: let rest = sum - top.
3. If rest == 1, the rest of the array is a single 1 and the answer is true.
4. If rest == 0 or rest >= top, no valid previous step exists — return false.
5. Otherwise replace the top with top mod rest and continue; a remainder of 0 is also impossible.

Why it works

The modulus is what makes this fast: with two elements the subtraction is a Euclidean algorithm, and stepping one subtraction at a time would take 10^9 rounds. The rest == 1 case has to be handled separately, precisely because top mod 1 is 0 even though [x, 1] can always be reduced.

Complexity

• Time — O(n log n + log(maxValue))
• Space — O(n)

Pitfalls

• Subtracting instead of taking the remainder times out on [10^9, 1].
• rest == 1 is a special case that the modulus alone gets wrong.
• A single-element array is reachable only when it is [1].

Reference solution

Python

from typing import List
import heapq

def isPossible(target: List[int]) -> bool:
    n = len(target)
    if n == 1:
        return target[0] == 1
    heap = [-v for v in target]
    heapq.heapify(heap)
    total = sum(target)
    while -heap[0] > 1:
        top = -heapq.heappop(heap)
        rest = total - top
        if rest == 1:
            return True
        if rest == 0 or rest >= top:
            return False
        prev = top % rest
        if prev == 0:
            return False
        total = rest + prev
        heapq.heappush(heap, -prev)
    return True

JavaScript

var isPossible = function(target) {
    var n = target.length, i;
    if (n === 1) return target[0] === 1;
    var heap = target.slice();
    var sift = function(j) {
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < heap.length && heap[l] > heap[s]) s = l;
            if (r < heap.length && heap[r] > heap[s]) s = r;
            if (s === j) break;
            var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
            j = s;
        }
    };
    for (i = Math.floor(heap.length / 2) - 1; i >= 0; i--) sift(i);
    var sum = 0;
    for (i = 0; i < n; i++) sum += target[i];
    while (heap[0] > 1) {
        var top = heap[0];
        var rest = sum - top;
        if (rest === 1) return true;
        if (rest === 0 || rest >= top) return false;
        var prev = top % rest;
        if (prev === 0) return false;
        sum = rest + prev;
        heap[0] = prev;
        sift(0);
    }
    return true;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Ways to Make Array With Product Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard
• Odd Even Jump Hard
• Maximum Number of Events That Can Be Attended II Hard