Construct Target Array with Multiple Sums

Problem#

Start with an array of n ones. In one step, replace any element with the sum of all elements. Given a target, return true iff target is reachable.

Examples#

target = [9, 3, 5] → true
target = [1, 1, 1, 2] → false

Constraints#

n <= 5 * 10^4, target[i] <= 10^9.

Hints#

Hint 1

Work backwards: the largest entry must have been the most-recently replaced; its predecessor = largest - sum(others) = largest mod sum(others).

Approach#

Reverse the process. Max-heap. Each step: pop the max m; let rest = totalSum - m. The predecessor was m - rest (or m mod rest to fast-forward many consecutive replacements of the same slot). Push it back. Stop when max is 1 or invalid.

Solution#

class Solution {
public:
    bool isPossible(vector<int>& target) {
        long long sum = 0;
        priority_queue<long long> pq;
        for (int x : target) { pq.push(x); sum += x; }
        while (pq.top() != 1) {
            long long m = pq.top(); pq.pop();
            long long rest = sum - m;
            if (rest <= 0 || rest >= m) return false;
            long long prev = m % rest;
            if (prev == 0) prev = rest; // can't be zero
            if (prev == m) return false;
            sum = sum - m + prev;
            pq.push(prev);
        }
        return true;
    }
};

import "container/heap"

type maxHeap []int

func (h maxHeap) Len() int            { return len(h) }
func (h maxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h maxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *maxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func isPossible(target []int) bool {
    sum := 0
    h := &maxHeap{}
    for _, x := range target {
        heap.Push(h, x)
        sum += x
    }
    for (*h)[0] != 1 {
        m := heap.Pop(h).(int)
        rest := sum - m
        if rest <= 0 || rest >= m {
            return false
        }
        prev := m % rest
        if prev == 0 {
            prev = rest
        }
        if prev == m {
            return false
        }
        sum = sum - m + prev
        heap.Push(h, prev)
    }
    return true
}

from typing import List
import heapq

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        total = sum(target)
        # max-heap via negation
        heap = [-x for x in target]
        heapq.heapify(heap)
        while -heap[0] != 1:
            m = -heapq.heappop(heap)
            rest = total - m
            if rest <= 0 or rest >= m:
                return False
            prev = m % rest
            if prev == 0:
                prev = rest
            if prev == m:
                return False
            total = total - m + prev
            heapq.heappush(heap, -prev)
        return True

class MaxHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    peek() { return this.h[0]; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] >= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                let best = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < n && this.h[l] > this.h[best]) best = l;
                if (r < n && this.h[r] > this.h[best]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
}

function isPossible(target) {
    let sum = 0;
    const pq = new MaxHeap();
    for (const x of target) { pq.push(x); sum += x; }
    while (pq.peek() !== 1) {
        const m = pq.pop();
        const rest = sum - m;
        if (rest <= 0 || rest >= m) return false;
        let prev = m % rest;
        if (prev === 0) prev = rest;
        if (prev === m) return false;
        sum = sum - m + prev;
        pq.push(prev);
    }
    return true;
}

class Solution {
    public boolean isPossible(int[] target) {
        long sum = 0;
        PriorityQueue<Long> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for (int x : target) {
            pq.offer((long) x);
            sum += x;
        }
        while (pq.peek() != 1) {
            long m = pq.poll();
            long rest = sum - m;
            if (rest <= 0 || rest >= m) return false;
            long prev = m % rest;
            if (prev == 0) prev = rest;
            if (prev == m) return false;
            sum = sum - m + prev;
            pq.offer(prev);
        }
        return true;
    }
}

class MaxHeap {
    private h: number[] = [];
    size(): number { return this.h.length; }
    peek(): number { return this.h[0]; }
    push(v: number): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] >= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): number {
        const top = this.h[0];
        const last = this.h.pop() as number;
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                let best = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < n && this.h[l] > this.h[best]) best = l;
                if (r < n && this.h[r] > this.h[best]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
}

function isPossible(target: number[]): boolean {
    let sum = 0;
    const pq = new MaxHeap();
    for (const x of target) { pq.push(x); sum += x; }
    while (pq.peek() !== 1) {
        const m = pq.pop();
        const rest = sum - m;
        if (rest <= 0 || rest >= m) return false;
        let prev = m % rest;
        if (prev === 0) prev = rest;
        if (prev === m) return false;
        sum = sum - m + prev;
        pq.push(prev);
    }
    return true;
}

Editorial#

The modulo m % rest is the speedup: if the same slot was the max for many consecutive operations, the predecessor sequence is m, m - rest, m - 2*rest, ... until it drops below rest. That terminal value is exactly m % rest. The prev == 0 guard handles the special case rest = 1 where the slot’s true predecessor is 1.

Complexity#

Time: O(n log n log max).
Space: O(n).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#