Construct Target Array With Multiple Sums

hard heap math reverse simulation

Problem

You begin with an array of n ones. In one move you pick any index, compute the sum of the whole array at that moment, and overwrite the chosen element with that sum. Given a target array of positive integers, decide whether some sequence of moves turns the all-ones array into exactly the target.

The array can hold up to 5·10⁴ elements and each value can be as large as 10⁹, so the sums explode far too fast to simulate forward.

Inputtarget = [9, 3, 5]

Outputtrue

[1,1,1] → [1,3,1] → [1,3,5] → [9,3,5]: each move writes the current sum into one slot.

target (comma-separated positive integers)

import heapq

def is_possible(target):
    total = sum(target)
    heap = [-x for x in target]
    heapq.heapify(heap)
    while True:
        largest = -heapq.heappop(heap)
        rest = total - largest
        if largest == 1 or rest == 1:
            return True
        if largest < rest or rest == 0 or largest % rest == 0:
            return False
        prev = largest % rest
        total = rest + prev
        heapq.heappush(heap, -prev)

function isPossible(target) {
  // a sorted array acts as the max-heap here (n is small)
  const heap = [...target].sort((a, b) => b - a);
  let total = target.reduce((s, v) => s + v, 0);
  while (true) {
    const largest = heap.shift();
    const rest = total - largest;
    if (largest === 1 || rest === 1) return true;
    if (largest < rest || rest === 0 || largest % rest === 0) return false;
    const prev = largest % rest;
    total = rest + prev;
    let i = 0;
    while (i < heap.length && heap[i] >= prev) i++;
    heap.splice(i, 0, prev);
  }
}

boolean isPossible(int[] target) {
    PriorityQueue<Long> heap = new PriorityQueue<>(Collections.reverseOrder());
    long total = 0;
    for (int v : target) { total += v; heap.offer((long) v); }
    while (true) {
        long largest = heap.poll();
        long rest = total - largest;
        if (largest == 1 || rest == 1) return true;
        if (largest < rest || rest == 0 || largest % rest == 0) return false;
        long prev = largest % rest;
        total = rest + prev;
        heap.offer(prev);
    }
}

bool isPossible(vector<int>& target) {
    priority_queue<long long> heap;
    long long total = 0;
    for (int v : target) { total += v; heap.push(v); }
    while (true) {
        long long largest = heap.top(); heap.pop();
        long long rest = total - largest;
        if (largest == 1 || rest == 1) return true;
        if (largest < rest || rest == 0 || largest % rest == 0) return false;
        long long prev = largest % rest;
        total = rest + prev;
        heap.push(prev);
    }
}

Explanation

Simulating forward is hopeless because the sums grow explosively and we would have to guess which index to overwrite at every move. The key insight is to run the process in reverse: a freshly written element equals the sum of the whole array, so it is strictly larger than everything else. That means the maximum of the target must be the last value written — pop it from a max-heap and undo that write.

If the popped maximum is largest and the other elements sum to rest = total − largest, then just before the write that slot held largest − rest. But subtracting one round at a time is far too slow when one element dwarfs the rest (think [10⁹, 1]). While the element stays bigger than rest it keeps being the maximum, so all those undo rounds collapse into a single jump: the slot's earlier value is largest % rest. That modulo is what makes the reverse simulation fast.

Three terminating cases close the loop. If largest == 1 the whole array is ones — the start state — so the answer is true. If rest == 1 the answer is also true: with a single 1 beside it, any value k walks down k → k−1 → … → 1. And if largest ≤ rest or largest % rest == 0 the undo would produce a value below 1, which is impossible, so the answer is false.

Walking the default example [9, 3, 5]: total is 17; pop 9, rest = 8, and 9 % 8 = 1, giving [5, 3, 1] with total 9. Pop 5, rest = 4, 5 % 4 = 1 → [3, 1, 1], total 5. Pop 3, rest = 2, 3 % 2 = 1 → [1, 1, 1]. The next pop sees largest = 1, so the target is reachable: true.

Each modulo step more than halves the popped value (the result is below both rest and largest − rest), so every element is popped only O(log M) times where M is the largest target value, and each heap operation costs O(log n). Overall the algorithm runs in roughly O(n · log M · log n) time with O(n) extra space for the heap.

Time: O(n · log M · log n) Space: O(n)