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); } 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; } };
|