GeezerVison is showing leetcodejavascript.com — #1354 - Construct Target Array With Multiple Sums - LeetCode JavaScript Solutions
Back to all solutions
#1354 - Construct Target Array With Multiple Sums
Problem Description
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.
Solution
/**
* @param {number[]} target
* @return {boolean}
*/
function isPossible(target) {
let totalSum = target.reduce((sum, num) => sum + num, 0);
const heap = [...target];
buildHeap();
while (heap[0] > 1) {
const largest = heap[0];
totalSum -= largest;
if (totalSum < 1) return false;
const newValue = largest - Math.floor((largest - 1) / totalSum) * totalSum;
if (newValue === largest) return false;
totalSum += newValue;
heap[0] = newValue;
heapifyDown(0);
}
return true;
function heapifyDown(index) {
let largest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
if (left < heap.length && heap[left] > heap[largest]) largest = left;
if (right < heap.length && heap[right] > heap[largest]) largest = right;
if (largest !== index) {
[heap[index], heap[largest]] = [heap[largest], heap[index]];
heapifyDown(largest);
}
}
function buildHeap() {
for (let i = Math.floor(heap.length / 2) - 1; i >= 0; i--) {
heapifyDown(i);
}
}
}