Construct Target Array With Multiple Sums

Hard
974.

Construct Target Array With Multiple Sums

HardArrayHeap (Priority Queue)MathGoogleAmazonMicrosoft

Construct Target Array With Multiple Sums is a hard coding problem on arrays, math and heap, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} target
 * @return {boolean}
 */
var isPossible = function(target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Construct Target Array With Multiple Sums — Solution

Construct Target Array With Multiple Sums solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Construct Target Array With Multiple Sums is a hard coding problem on arrays, math and heap, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Hard
  • Topics: Arrays, Math, Heap
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Construct Target Array With Multiple Sums

  1. Hint 1

    Run the process backwards: the largest element must have been the most recent sum.

  2. Hint 2

    Before that step it held largest - (sum of the others).

  3. Hint 3

    Subtracting repeatedly is slow when the others are small — use the remainder instead.

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

Java

public static boolean isPossible(int[] target) {
    int n = target.length;
    if (n == 1) return target[0] == 1;
    PriorityQueue<Long> heap = new PriorityQueue<>(Comparator.reverseOrder());
    long total = 0;
    for (int v : target) {
        heap.add((long) v);
        total += v;
    }
    while (heap.peek() > 1) {
        long top = heap.poll();
        long rest = total - top;
        if (rest == 1) return true;
        if (rest == 0 || rest >= top) return false;
        long prev = top % rest;
        if (prev == 0) return false;
        total = rest + prev;
        heap.add(prev);
    }
    return true;
}

C++

bool isPossible(vector<int>& target) {
    int n = (int) target.size();
    if (n == 1) return target[0] == 1;
    priority_queue<long long> heap;
    long long total = 0;
    for (int v : target) {
        heap.push(v);
        total += v;
    }
    while (heap.top() > 1) {
        long long top = heap.top();
        heap.pop();
        long long rest = total - top;
        if (rest == 1) return true;
        if (rest == 0 || rest >= top) return false;
        long long prev = top % rest;
        if (prev == 0) return false;
        total = rest + prev;
        heap.push(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Heaps and Priority Queues