Subramanya's Digital Garden

Recent Notes

1354. Construct Target Array With Multiple Sums

2 min read

links: Algorithms MOC

Construct Target Array with multiple sums

Problem:

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.

Approach:

This Problem assumes you have knowledge on following topics:

  1. Heaps
  2. Priority Queue

Approach 1

Greedy solution.

If you can build a target array from 1’s array, you can reverse the target array to 1’s following reverse steps

/**
 * @param {number[]} target
 * @return {boolean}
 */
 var isPossible = function(target) {
  // 1. find largest element in target
  // 2. replace the largest element with the difference of largest element and sum of all elements (except large element)
  // repeat until you get all 1's
  
  while (true) {
    let sum = target.reduce((acc, curVal) => acc + curVal)  
    // which means all the elements in target are 1
    if(sum === target.length) return true
 
    let maxNumberInTarget, maxNumberIndexInTarget;
    
    // find the largest number and it's index in array
    maxNumberInTarget = -Infinity
    
    target.forEach((elem, index) => {
      if(elem > maxNumberInTarget) {
        maxNumberInTarget = elem
        maxNumberIndexInTarget = index
      }
    })
    
    // remove largest number from the sum
    const sumExcludingMax = sum - maxNumberInTarget
    
    // consider example of [9, 3, 7]
    // sum = 19
    // sum -= maxNumInTarget becomes 19 - 9 = 10
    // maxNumberInTarget is 9 and sum is 10 when subtracted becomes -1 less than 0, so can't make array with all 1's
    if (maxNumberInTarget <= sumExcludingMax || sumExcludingMax === 0) return false
    target[maxNumberIndexInTarget] = maxNumberInTarget - sumExcludingMax * (maxNumberInTarget / sumExcludingMax | 0) || sumExcludingMax
  }  
};
 
console.log(isPossible([8, 5]))

tags: heap priority-queue

sources:

Graph View