Construct Target Array With Multiple Sums

Problem

You are given an array target of n integers. From a starting array arr consisting of n 1's, you may perform the following procedure :

• let x be the sum of all elements currently in your array.
• choose index i, such that 0 <= i < n and set the value of arr at index i to x.
• You may repeat this procedure as many times as needed.

Return true if it is possible to construct the target array from arr, otherwise, return false.

Examples

Example 1:

Input: target = [9,3,5]
Output: true
Explanation: Start with arr = [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

Example 2:

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].

Example 3:

Input: target = [8,5]
Output: true

Constraints

• n == target.length
• 1 <= n <= 5 * 10^4
• 1 <= target[i] <= 10^9

Solution

The approach is similar to [Reaching Points](reaching-points).

The first solution uses a heap and has O(n log n) time complexity. The second solution is optimized per the complexity analysis to run in O(n) time.

Method 1 – Reverse Thinking Using Modulo Operator and Max Heap

Intuition

The key insight is to work backwards from the target array, always focusing on the largest element. Since each operation sets one element to the sum of the array, the largest element at any step must have been formed by adding up the previous array. By reversing the process and using a max heap, we can efficiently simulate the steps needed to reach the starting array of all ones.

Approach

1. Max Heap:

   • Use a max heap to always access the largest element in the array.

2. Reverse Simulation:

   • At each step, remove the largest element (cur) from the heap.
   • The sum of the rest of the elements is sum - cur.
   • The previous value at this position must have been cur - (sum - cur), or more efficiently, cur % (sum - cur).
   • If the previous value is less than 1 or unchanged, it's impossible to reach the starting array.
   • Add the previous value back to the heap and update the sum.

3. Edge Cases:

   • If the sum of the rest is 1, we can always reach the starting array.
   • If the largest element is 1, continue.

4. Repeat:

   • Continue until all elements are 1.

Dry Run

Let's walk through an example:

Suppose target = [9, 3, 5].

Step 1: Initialize

• Calculate the sum: sum = 9 + 3 + 5 = 17
• Build a max heap: pq = [9, 3, 5]

Step 2: First Iteration

• Remove the largest element: cur = 9
• Remaining sum: rest = 17 - 9 = 8
• Previous value: prev = 9 % 8 = 1
• Add 1 back: pq = [5, 3, 1], sum = 8 + 1 = 9

Step 3: Second Iteration

• Remove the largest element: cur = 5
• Remaining sum: rest = 9 - 5 = 4
• Previous value: prev = 5 % 4 = 1
• Add 1 back: pq = [3, 1, 1], sum = 4 + 1 = 5

Step 4: Third Iteration

• Remove the largest element: cur = 3
• Remaining sum: rest = 5 - 3 = 2
• Previous value: prev = 3 % 2 = 1
• Add 1 back: pq = [1, 1, 1], sum = 2 + 1 = 3

Step 5: Termination

• All elements are now 1, so return true.

At each step, the largest element is reduced efficiently using modulo, and the process continues until all elements are 1.

Gotchas

Be aware of these common pitfalls:

• The sum of all elements can exceed INT_MAX, so always use a 64-bit integer for the running sum.
• If the largest element is less than or equal to the sum of the rest, it's impossible to proceed—return false in this case.
• If the sum of the rest is 1, you can always reach the starting array (all ones)—return true immediately.
• If the largest element is much greater than the sum of the rest, repeated subtraction is inefficient and can cause TLE. Use the modulo operation (cur % rest) to quickly reduce the value.
  • For example, with target = [10, 3]:
    • Without %: [10, 3] -> [7, 3] -> [4, 3] -> [1, 3] (many steps)
    • With %: [10, 3] -> [1, 3] (one step)
• If the modulo result is zero, return false—this means you cannot reach the starting array.
• Special case: If rest == 1, always return true (e.g., [100, 1]).

Finally, if the sum equals the number of elements, you have reached the starting array of all ones.

Code

C++

#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
    bool isPossible(vector<int>& target) {
        long long sum = 0;
        priority_queue<long long> pq;
        for (int x : target) {
            sum += x;
            pq.push(x);
        }
        while (pq.top() > 1) {
            long long cur = pq.top(); pq.pop();
            long long rest = sum - cur;
            if (rest == 1) return true;
            if (rest == 0 || cur <= rest) return false;
            long long prev = cur % rest;
            if (prev == 0) return false;
            pq.push(prev);
            sum = rest + prev;
        }
        return true;
    }
};

Go

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{} { n := len(*h); x := (*h)[n-1]; *h = (*h)[:n-1]; return x }
func isPossible(target []int) bool {
    h := &MaxHeap{}
    sum := 0
    for _, x := range target {
        heap.Push(h, x)
        sum += x
    }
    for (*h)[0] > 1 {
        cur := heap.Pop(h).(int)
        rest := sum - cur
        if rest == 1 { return true }
        if rest == 0 || cur <= rest { return false }
        prev := cur % rest
        if prev == 0 { return false }
        heap.Push(h, prev)
        sum = rest + prev
    }
    return true
}

Java

import java.util.*;
class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        long sum = 0;
        for (int x : target) {
            sum += x;
            pq.add(x);
        }
        while (pq.peek() > 1) {
            int cur = pq.poll();
            long rest = sum - cur;
            if (rest == 1) return true;
            if (rest == 0 || cur <= rest) return false;
            int prev = (int)(cur % rest);
            if (prev == 0) return false;
            pq.add(prev);
            sum = rest + prev;
        }
        return true;
    }
}

Kotlin

import java.util.PriorityQueue
class Solution {
    fun isPossible(target: IntArray): Boolean {
        val pq = PriorityQueue<Int>(compareByDescending { it })
        var sum = 0L
        for (x in target) {
            sum += x
            pq.add(x)
        }
        while (pq.peek() > 1) {
            val cur = pq.poll()
            val rest = sum - cur
            if (rest == 1L) return true
            if (rest == 0L || cur <= rest) return false
            val prev = (cur % rest).toInt()
            if (prev == 0) return false
            pq.add(prev)
            sum = rest + prev
        }
        return true
    }
}

Python

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

Rust

use std::collections::BinaryHeap;
impl Solution {
    pub fn is_possible(target: Vec<i32>) -> bool {
        let mut pq = BinaryHeap::new();
        let mut sum: i64 = 0;
        for &x in &target {
            pq.push(x as i64);
            sum += x as i64;
        }
        while let Some(&cur) = pq.peek() {
            if cur == 1 { break; }
            let cur = pq.pop().unwrap();
            let rest = sum - cur;
            if rest == 1 { return true; }
            if rest == 0 || cur <= rest { return false; }
            let prev = cur % rest;
            if prev == 0 { return false; }
            pq.push(prev);
            sum = rest + prev;
        }
        true
    }
}

TypeScript

function isPossible(target: number[]): boolean {
    let sum = target.reduce((a, b) => a + b, 0);
    const pq = [...target];
    pq.sort((a, b) => b - a);
    while (pq[0] > 1) {
        let cur = pq.shift()!;
        let rest = sum - cur;
        if (rest === 1) return true;
        if (rest === 0 || cur <= rest) return false;
        let prev = cur % rest;
        if (prev === 0) return false;
        pq.push(prev);
        sum = rest + prev;
        pq.sort((a, b) => b - a);
    }
    return true;
}

Complexity

• ⏰ Time complexity: O(n log n), where n is the length of target. Each heap operation takes O(log n) time, and we may perform up to O(n) such operations.
• 🧺 Space complexity: O(n) for the heap and auxiliary variables.

Further Details

In Java, building the heap is O(n log n) since there is no direct buildHeap method; otherwise, it could be O(n). The number of operations is effectively capped: for the worst-case input like [1, 1], it takes at most 44 steps before integer overflow, and for larger arrays (e.g., size 5 * 10^4), it takes even fewer (about 16 steps). If the same element is updated repeatedly, the modulo operation ensures its value drops rapidly, so the process does not take excessive time. Since all numbers are integers, the sum cannot exceed INT_MAX.

Method 2 – Iterative Max-Index Update

Intuition

The main idea is to always focus on the largest element in the array, since it must have been formed by adding up all the other elements in a previous step. By repeatedly reducing the largest element using the sum of the rest, we can simulate the reverse process efficiently. If at any point the largest element cannot be reduced further or the process becomes invalid, we know it's impossible to reach the starting array.

Approach

1. Find the Maximum:
   • At each step, identify the index of the largest element in the array.
2. Update the Largest Element:
   • Subtract the largest element from the total sum to get the sum of the rest.
   • If the sum of the rest is 1, we can always reach the starting array (all ones).
   • If the largest element is less than or equal to the sum of the rest, or the sum of the rest is zero, return false.
   • Replace the largest element with its value modulo the sum of the rest.
   • If the result is zero or unchanged, return false.
   • Update the total sum accordingly.
3. Repeat:
   • Continue this process until all elements are 1 (i.e., the sum equals the array's length).

Code

C++

class Solution {
public:
    bool isPossible(vector<int>& t) {
        long long s = 0;
        for (int n : t) s += n;
        while (true) {
            int mi = 0;
            for (int i = 1; i < t.size(); ++i) if (t[i] > t[mi]) mi = i;
            long long rest = s - t[mi];
            if (t[mi] == 1 || rest == 1) return true;
            if (rest == 0 || t[mi] <= rest) return false;
            int prev = t[mi] % rest;
            if (prev == 0) return false;
            s = rest + prev;
            t[mi] = prev;
        }
    }
};

Go

func isPossible(t []int) bool {
    s := 0
    for _, n := range t {
        s += n
    }
    for {
        mi := 0
        for i := 1; i < len(t); i++ {
            if t[i] > t[mi] {
                mi = i
            }
        }
        rest := s - t[mi]
        if t[mi] == 1 || rest == 1 {
            return true
        }
        if rest == 0 || t[mi] <= rest {
            return false
        }
        prev := t[mi] % rest
        if prev == 0 {
            return false
        }
        s = rest + prev
        t[mi] = prev
    }
}

Java

class Solution {
    public boolean isPossible(int[] t) {
        long s = 0;
        for (int n : t) s += n;
        while (true) {
            int mi = 0;
            for (int i = 1; i < t.length; ++i) if (t[i] > t[mi]) mi = i;
            long rest = s - t[mi];
            if (t[mi] == 1 || rest == 1) return true;
            if (rest == 0 || t[mi] <= rest) return false;
            int prev = (int)(t[mi] % rest);
            if (prev == 0) return false;
            s = rest + prev;
            t[mi] = prev;
        }
    }
}

Kotlin

class Solution {
    fun isPossible(t: IntArray): Boolean {
        var s = t.sum().toLong()
        while (true) {
            var mi = 0
            for (i in 1 until t.size) if (t[i] > t[mi]) mi = i
            val rest = s - t[mi]
            if (t[mi] == 1 || rest == 1L) return true
            if (rest == 0L || t[mi] <= rest) return false
            val prev = (t[mi] % rest).toInt()
            if (prev == 0) return false
            s = rest + prev
            t[mi] = prev
        }
    }
}

Python

class Solution:
    def isPossible(self, t: list[int]) -> bool:
        s = sum(t)
        while True:
            mi = max(range(len(t)), key=lambda i: t[i])
            rest = s - t[mi]
            if t[mi] == 1 or rest == 1:
                return True
            if rest == 0 or t[mi] <= rest:
                return False
            prev = t[mi] % rest
            if prev == 0:
                return False
            s = rest + prev
            t[mi] = prev

Rust

impl Solution {
    pub fn is_possible(mut t: Vec<i32>) -> bool {
        let mut s: i64 = t.iter().map(|&x| x as i64).sum();
        loop {
            let mi = t.iter().enumerate().max_by_key(|&(_, &v)| v).unwrap().0;
            let rest = s - t[mi] as i64;
            if t[mi] == 1 || rest == 1 { return true; }
            if rest == 0 || (t[mi] as i64) <= rest { return false; }
            let prev = (t[mi] as i64) % rest;
            if prev == 0 { return false; }
            s = rest + prev;
            t[mi] = prev as i32;
        }
    }
}

TypeScript

function isPossible(t: number[]): boolean {
    let s = t.reduce((a, b) => a + b, 0);
    while (true) {
        let mi = 0;
        for (let i = 1; i < t.length; ++i) if (t[i] > t[mi]) mi = i;
        let rest = s - t[mi];
        if (t[mi] === 1 || rest === 1) return true;
        if (rest === 0 || t[mi] <= rest) return false;
        let prev = t[mi] % rest;
        if (prev === 0) return false;
        s = rest + prev;
        t[mi] = prev;
    }
}

Complexity

• ⏰ Time complexity: O(n^2), since in the worst case, for each update, we scan the array to find the maximum, and this can happen up to O(n) times for each element.
• 🧺 Space complexity: O(1), as we only use a constant amount of extra space beyond the input array.