[LeetCode] Construct Target Array With Multiple Sums

1354. Construct Target Array With Multiple Sums

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
bool isPossible(vector<int>& target) {
if(target.size() == 1) return target[0] == 1;
priority_queue<int> pq;
long long sum = 0;
for(auto& t : target) {
sum += t;
pq.push(t);
}
// max value = remain * n + prev value
// find n and make max value to prev value
while(pq.top() != 1) {
long long tp = pq.top(); pq.pop();
long long stp = pq.top();
long long remain = sum - tp;
long long n = ceil(1.0 * (sum - stp) / remain) - 1;
long long origin = tp - n * remain;
if(origin == tp) origin = tp * 2 - sum;
if(origin < 1) return false;
pq.push(origin);
sum = sum - tp + origin;
}

return true;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/25/PS/LeetCode/construct-target-array-with-multiple-sums/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.