[LeetCode] 1354. Construct Target Array with Multiple Sums

Problem

Image is linked to LeetCode problem page

Explanation

Constructing the target array forward from `[1, 1, …, 1]` is infeasible because each step allows any element to be replaced by the sum of the array, leading to an exponential number of possible sequences. Instead, we reverse the process and work backward FROM the target array to determine whether it can be reduced to the base case.

Why Max Heap?
When reversing the process, the element that must be reduced is always the current maximum. A max heap is used to efficiently identify and update this element at each step.

 

Assume that before a sequence of updates, the array was `[x_0, x_1, …, x_i]` and after `k` updates to the element at position `i`, it became `[x_0, x_1, ..., x_{i-1}, M].`

Let ``S = x_0 + x_1 + … + x_{i-1}`` denote the constant sum of the unchanged elements. 

 

Each forward update replaces the element at position `i` with the total sum of the array. Since other elements remain fixed, each update adds exactly `S` to the current element. Therefore, we can visualize the growth of this element as a linear progression:

``
\begin{aligned}
\text{sum}_1 &= S + x_i \\
\text{sum}_2 &= S + \text{sum}_1 = 2S + x_i \\
\text{sum}_3 &= S + \text{sum}_2 = 3S + x_i \\
\vdots \\
M &= (k-1)S + x_i \\
\text{sum}_k &= S + M = kS + x_i
\end{aligned}
`` To reverse this process, we need to solve for `x_i`. From the equation `M = (k-1)S + x_i`, we can see that `x_i` is simply the remainder when `M` is divided by `S`: ``x_i = M\bmod S.`` 

During the reverse process, several configurations indicate whether the target array can or cannot originate from all ones: 

• If `S = 0`, the target array contains only a single element `M` which is greater than 1 (example: `[2]`), which is impossible to construct from all ones.
• If `S>=M`, then `x = M\bmod S` is equivalent to `x = M`, hence the array cannot be reduced any further. 
• If `S=1`, then the array has the form `[M, 1]`. In this case, the maximum can always be reduced to one, so the configuration is valid. 
• If `x=0`, no valid array state would contain zero since we start with an array of all 1s, so the configuration is invalid.

Solution

#include <queue>
#include <vector>

class Solution {
public:
    bool isPossible(vector<int>& target) {
        std::priority_queue<int> maxHeap;
        long long sum = 0;
        for(int t: target) {
            maxHeap.push(t);
            sum+=t;
        }
        while(maxHeap.top() > 1) {
            int M = maxHeap.top();
            maxHeap.pop();
            sum -= M; 
            if(sum == 0 || sum >= M) return false;
            if(sum == 1) return true;
            M %= sum;
            if(M == 0) return false;
            sum += M;
            maxHeap.push(M);
        }
        return true;
    }
};