Problem Description

Given an array target of integers, you start with an array arr of the same length, where every element is 1. You are allowed to perform the following operation any number of times:

• Choose an index i and set arr[i] = sum(arr) (i.e., replace one element with the sum of the entire array).

Your task is to determine if it is possible to construct the target array from arr using this operation any number of times.

Key Constraints:

• All elements in target are positive integers.
• There is only one valid solution for each test case.
• You may not reuse or skip elements in the operation.

Thought Process

At first glance, the problem seems to ask if we can build up to the target array by repeatedly replacing elements with the sum of the current array. A brute-force approach might try all possible sequences of operations, but this quickly becomes infeasible for large arrays or large numbers.

Observing the operation closely, we realize that every time we perform it, one element becomes much larger, and the sum increases rapidly. This suggests that instead of simulating every operation forward, it might be easier to work backwards: can we reduce target to an array of all ones by reversing the allowed operation?

This reversal leads to a key insight: at each step, the largest number in target must have been formed by summing the previous array and replacing one element. Thus, we can try to "undo" this operation by repeatedly reducing the largest element by the sum of the rest.

Solution Approach

To solve the problem efficiently, we use a max-heap (priority queue) to always access the largest element in target. Here’s a step-by-step breakdown:

1. Initialize a max-heap: Insert all elements of target into a max-heap for quick access to the largest number.
2. Track the total sum: Maintain the sum of all elements for each iteration.
3. Reverse the operation: While the largest element is greater than 1:
   • Pop the largest element (max_elem).
   • Compute the sum of the remaining elements (rest_sum = total_sum - max_elem).
   • If rest_sum == 1, then we can always reach the target by repeatedly subtracting 1, so return True.
   • If rest_sum == 0 or max_elem <= rest_sum, return False (invalid scenario).
   • Otherwise, the previous value of max_elem must have been max_elem % rest_sum (since in one step, we could have added rest_sum multiple times).
   • If the new value is 0 or unchanged, return False.
   • Push the new value back into the heap and update the total sum.
4. Finish: If all elements become 1, return True.

Why a heap? Using a max-heap allows us to efficiently find and update the largest element in each step, which is crucial for performance.

Example Walkthrough

Sample Input: target = [9, 3, 5]

1. Initial heap: [9, 3, 5], total sum = 17
2. Pop 9 (largest), rest_sum = 8. Previous value: 9 % 8 = 1.
   Push 1 back. Heap: [5, 3, 1], total sum = 9
3. Pop 5, rest_sum = 4. Previous value: 5 % 4 = 1.
   Push 1 back. Heap: [3, 1, 1], total sum = 5
4. Pop 3, rest_sum = 2. Previous value: 3 % 2 = 1.
   Push 1 back. Heap: [1, 1, 1], total sum = 3
5. All elements are 1. Return True.

Explanation: Each time, we "undo" the operation by reducing the largest number, eventually reaching all ones.

Time and Space Complexity

Brute-force approach: Would explore every possible sequence of operations, leading to exponential time complexity: O(k^n) where k is the average value and n is the array length.

Optimized approach (heap-based):

• Each heap operation (pop/push) is O(\log n).
• The number of iterations is proportional to the sum of the elements, but since we reduce the largest number significantly each time (by modulo), the total number of steps is bounded by O(\log S) where S is the sum of array elements.
• Total time complexity: O(n \log n + k \log n) where k is the number of reduction steps.
• Space complexity: O(n) for the heap.

Summary

The key insight is to simulate the process in reverse using a max-heap, always reducing the largest element by the sum of the rest, and efficiently checking for invalid configurations. This transforms what could be an exponential-time problem into a highly efficient solution. The use of heaps and modulo arithmetic makes the approach both elegant and practical for large inputs.

Code Implementation

import heapq

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

#include <queue>
#include <vector>
using namespace std;

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

import java.util.*;

class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        long total = 0;
        for (int num : target) {
            pq.add(num);
            total += num;
        }
        while (true) {
            int largest = pq.poll();
            long rest = total - largest;
            if (largest == 1 || rest == 1) return true;
            if (rest == 0 || largest <= rest) return false;
            int x = (int)(largest % rest);
            if (x == 0) return false;
            pq.add(x);
            total = rest + x;
        }
    }
}
      

class MaxHeap {
    constructor(arr) {
        this.heap = arr.slice();
        this.heapify();
    }
    heapify() {
        this.heap.sort((a, b) => b - a);
    }
    pop() {
        return this.heap.shift();
    }
    push(val) {
        this.heap.push(val);
        this.heapify();
    }
    size() {
        return this.heap.length;
    }
}

var isPossible = function(target) {
    let total = target.reduce((a, b) => a + b, 0);
    let heap = new MaxHeap(target);
    while (true) {
        let largest = heap.pop();
        let rest = total - largest;
        if (largest === 1 || rest === 1) return true;
        if (rest === 0 || largest <= rest) return false;
        let x = largest % rest;
        if (x === 0) return false;
        heap.push(x);
        total = rest + x;
    }
};