Solution Explanation: Construct Target Array With Multiple Sums

This problem asks whether it's possible to construct a target array from an initial array of all 1s by repeatedly summing all elements and replacing one element with that sum. A straightforward forward approach is complex. The efficient solution leverages a reverse construction strategy using a priority queue (max-heap).

Algorithm:

1. Initialization:

   • Calculate the sum s of all elements in target.
   • Create a max-heap pq containing the negated elements of target. Using a max-heap ensures we always work with the largest element.

2. Iterative Construction (Reverse):

   • While the largest element in pq (the absolute value of the top element) is greater than 1:
     • Extract the largest element mx from pq.
     • Calculate t, the sum of all remaining elements ( s - mx).
     • Check for Impossibility: If t is 0 (all other elements were 0) or mx - t < 1 (the largest element cannot be created from the sum of the others), then it's impossible to construct the target array; return false.
     • Calculate x, the remainder after dividing mx by t. If x is 0, use t instead (to avoid unnecessarily large values).
     • Push -x back onto the pq.
     • Update s to reflect the change.

3. Success: If the loop completes without returning false, it means all elements have been reduced to 1. Return true.

Time Complexity: O(n log n)

The dominant operations are heap operations (insertion, extraction, and heapify). There are at most n such operations as we process each element. The heap operations take O(log n) time each.

Space Complexity: O(n)

The space used is primarily for the priority queue which stores at most n elements.

Code Examples (Python and Java):

Python:

import heapq
 
class Solution:
    def isPossible(self, target: List[int]) -> bool:
        s = sum(target)
        pq = [-x for x in target]  # Negate for max-heap
        heapq.heapify(pq)
 
        while -pq[0] > 1:  # Check the largest element
            mx = -heapq.heappop(pq)
            t = s - mx
            if t == 0 or mx - t < 1:
                return False
            x = mx % t or t  # Handle the case where mx is perfectly divisible by t
            heapq.heappush(pq, -x)
            s = s - mx + x
 
        return True
 

Java:

import java.util.*;
 
class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder()); // Max-heap
        long s = 0;
        for (int x : target) {
            s += x;
            pq.offer((long) x); // Use Long to handle large sums
        }
 
        while (pq.peek() > 1) {
            long mx = pq.poll();
            long t = s - mx;
            if (t == 0 || mx - t < 1) {
                return false;
            }
            long x = mx % t;
            if (x == 0) x = t;  // Handle perfect divisibility
            pq.offer(x);
            s = s - mx + x;
        }
 
        return true;
    }
}

The other languages (C++, Go, TypeScript) follow a very similar structure, adapting the priority queue implementation to their respective standard libraries. The core algorithm remains the same.