1354-construct-target-array-with-multiple-sums.js

/**
 * 1354. Construct Target Array With Multiple Sums
 * https://leetcode.com/problems/construct-target-array-with-multiple-sums/
 * Difficulty: Hard
 *
 * 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.
 */

/**
 * @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);
    }
  }
}