Construct Target Array With Multiple Sums

Given an array of integers target. From a starting array, A consisting of all 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 < target.size and set the value of A 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 A otherwise return False.

Example 1:

Input: target = [9,3,5]
Output: true
Explanation: Start with [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 <= target.length <= 5 * 10^4
• 1 <= target[i] <= 10^9

Approach:

We can try to reconstruct the target array in backwards fashion to starting array A. If we are able to do this correctly, we know that it's possible to construct target from A.

For this, we need to observe that everytime a replacement will form a new largest element in target. This means the largest element in target was formed by the last replacement.

Thus we can reconstruct the array before the last replacement by subtracting sum of rest of elements of array from largest element (since in forward procedure we are summing up array and replacing an element with it, so in the reverse simulation we are doing the opposite). This step will be repeated till all the elements in target either become 1 (return true) or some element becomes less than 1 (return false).

To efficiently get the largest element from array after each step, we will maintain a max-heap. Everytime we will take out largest element, subtract rest of the array from it and push the modifed element back in.

This may still lead to TLE problems in target arrays such as [1, 1000000000] where subtracting sum of rest of array restArrSum from largest element one at a time may take a lot of time. So, we will subtract restArrSum * n from the largest element (equivalent to subtracting restArrSum n times from the largest), where n is the least number of subtractions required to make the largest element less than 2nd largest element.

C++ Solution:

class Solution {
public:
    bool isPossible(vector<int>& target) {
        priority_queue<int> q;
        long sum = 0;
        
        for (auto num : target) {
            q.push(num);
            sum += num;
        }
        
        while (!q.empty()) {
            int curr_max = q.top();
            q.pop();
            if (curr_max == 1) return true;
            long rest = sum - curr_max;
            
            if (rest == 0) return false;
            if (rest == 1) return true;
            if(rest >= curr_max) return false;
            rest = curr_max % rest;
            if (rest == 0) return false;
            
            sum -= (curr_max - rest);
            q.push(rest);
        }
        return true;
    }
};

Time Complexity : O(N + KlogN), where N is the number of elements in target and K is the total sum of target elements. We require O(N) time complexity to construct max-heap from target. Then at each iteration, we can see that sum / total is atleast reduced by half. So, the max number of iteration required will be log2(K), with each iteration requiring O(logN) time complexity for push and pop operations. Thus the total time complexity becomes - O(N + KlogN).

Space Complexity : O(N), required to maintain the Max-Heap.

💻🐱‍💻If there are any suggestions / questions / mistakes in my post, please do comment below 👇