Problem Explanation

This problem asks to determine whether we can form the given target array from the initial array that contains all 1's. The procedure we can perform is to compute the sum of the current array elements (let's call it sum) and select an index i from the target array, then replace the value at index i in the starting array with 'sum'.

The constraints on the length of the target array and the values in the target array make this problem quite challenging, as exhaustively trying every possible replacement of elements will not run within the time limits.

Walkthrough

Let's consider an example target array, [9, 3, 5]. The initial array is [1, 1, 1].

• In the first step, we can select index 2. The sum of the initial array is 3 so replace the element at index 2 in the initial array with sum: [1, 1, 3].
• In the second step, we can select index 1. The sum is now 5, so replace the value at index 1 with 5: [1, 5, 3].
• In the third step, we can select index 0. The sum is now 9, so replace the value at index 0 with 9: [9, 5, 3].
• Now the starting array equals to the target array.

Approach

The main idea for the solution is to maintain a priority queue (also known as a heap) to keep track of the largest element in the current Array. This is because the sum we calculate will be used to replace the largest element in the array. But it's not enough just to reduce the largest number by sum. If the rest of the numbers in the array add up to less than the largest number, we will end up in an infinite loop of decreasing the largest number and increasing the sum. To avoid this, we take the largest number modulo the sum of the rest of the array numbers, updating the sum in the process. This step "simulates" the process of reducing the largest number back to the sum of the rest of the array, then adding the sum back to one of the numbers.

We do these updates until the largest number is 1, or we can't perform updates without violating the constraints or changing the largest number. If the largest number is 1, it means that all numbers are 1, and we have the starting state of the problem.

Python Solution

1
2python
3import heapq
4
5class Solution:
6    def isPossible(self, target):
7        total = sum(target)
8        maxHeap = [-ele for ele in target]
9        heapq.heapify(maxHeap)
10        
11        while True:
12            ele = -heapq.heappop(maxHeap)
13            total -= ele
14            if ele == 1 or total == 1:
15                return True
16            if ele < total or total == 0 or ele % total == 0:
17                return False
18            ele %= total
19            total += ele
20            heapq.heappush(maxHeap, -ele)

Java Solution

1
2java
3public class Solution {
4    public boolean isPossible(int[] target) {
5        long total = 0;
6        int n = target.length;
7        PriorityQueue<Long> pq = new PriorityQueue<>(n, (a, b) -> Long.compare(b, a));
8        for (int a : target) {
9            total += a;
10            pq.add((long) a);
11        }
12        while (true) {
13            long a = pq.poll();
14            total -= a;
15            if (a == 1 || total == 1)
16                return true;
17            if (a < total || total == 0 || a % total == 0)
18                return false;
19            a %= total;
20            total += a;
21            pq.add(a);
22        }
23    }
24}

Javascript Solution

1
2javascript
3/**
4 * @param {number[]} target
5 * @return {boolean}
6 */
7var isPossible = function(target) {
8    let sum = target.reduce((a, b) => a + b, 0);
9    let maxHeap = new MaxHeap(target);
10    
11    while (true) {
12        let num = maxHeap.poll();
13        sum -= num;
14        if (num === 1 || sum === 1) {
15            return true;
16        }
17        if (num < sum || sum === 0 || num % sum === 0) {
18            return false;
19        }
20        num %= sum;
21        sum += num;
22        maxHeap.offer(num);
23    }
24};

C# Solution

1
2csharp
3public class Solution {
4    public bool IsPossible(int[] target) {
5        long total = 0;
6        int n = target.Length;
7        var maxHeap = new MaxHeap(n);
8        foreach (var num in target)
9        {
10            total += num;
11            maxHeap.Add(num);
12        }
13        while (true) 
14        {
15            var num = maxHeap.Poll();
16            total -= num;
17            if (num == 1 || total == 1)
18                return true;
19            if (num < total || total == 0 || num % total == 0)
20                return false;
21            num %= total;
22            total += num;
23            maxHeap.Add(num);
24        }
25    }
26}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool isPossible(vector<int>& target) {
6        long total = 0;
7        int n = target.size();
8        priority_queue<long> pq;
9        for (int a : target) {
10            total += a;
11            pq.push(a);
12        }
13        while (true) {
14            long a = pq.top(); pq.pop();
15            total -= a;
16            if (a == 1 || total == 1)
17                return true;
18            if (a < total || total == 0 || a % total == 0)
19                return false;
20            a %= total;
21            total += a;
22            pq.push(a);
23        }
24    }
25};

For JavaScript and C#

JavaScript and C# do not have a built-in max heap structure. The following are heap solutions for these languages.

JavaScript Solution

We create a custom class for the heap with methods to add to the heap, remove from the heap, and get the max value.

1
2javascript
3class MaxHeap {
4    constructor(array) {
5        this.array = array;
6        this.size = array.length;
7        this.buildHeap();
8    }
9    
10    buildHeap() {
11        for (let i = Math.floor(this.size / 2) - 1; i >= 0; i--) {
12            this.heapify(i);
13        }
14    }
15    
16    heapify(i) {
17        while (true) {
18            let left = 2 * i + 1;
19            let right = 2 * i + 2;
20            let largest = i;
21            
22            if (left < this.size && this.array[left] > this.array[largest]) {
23                largest = left;
24            }
25            
26            if (right < this.size && this.array[right] > this.array[largest]) {
27                largest = right;
28            }
29            
30            if (i === largest) break;
31            
32            [this.array[i], this.array[largest]] = [this.array[largest], this.array[i]];
33            i = largest;
34        }
35    }
36    
37    poll() {
38        let max = this.array[0];
39        this.array[0] = this.array[this.size - 1];
40        this.size--;
41        this.heapify(0);
42        return max;
43    }
44    
45    add(val) {
46        this.array[this.size] = val;
47        this.size++;
48        this.buildHeap();
49    }
50}

C# Solution

For C#, we can use SortedSet which keeps items sorted and duplicates are merged.

1
2csharp
3public class Solution {
4    public bool IsPossible(int[] target) {
5        long total = 0;
6        var maxHeap = new SortedSet<(int val, int index)>();
7        for (int i = 0; i < target.Length; i++) {
8            total += target[i];
9            maxHeap.Add((target[i], i));
10        }
11        while (true) {
12            var max = maxHeap.Max;
13            maxHeap.Remove(max);
14            total -= max.val;
15            if (max.val == 1 || total == 1) return true;
16            if (max.val < total || total == 0 || max.val % total == 0) return false;
17            maxHeap.Add(((int)(max.val % total), max.index));
18            total += max.val % total;
19        }
20    }
21}