Create JavaScript function to fulfills the condition price and pcs

Question

Create JavaScript function (price, pcs)

With denomination

[100000, 50000, 20000, 10000, 5000, 2000, 1000]

So

function(40000, 4) return [10000, 10000, 10000, 10000]
function(10000, 4) return [5000, 2000, 2000, 1000]
function(40000, 2) return [20000, 20000]
function(50000, 2) return [] //  because there is no 25000 in denomination.

The length of result array must match the 'pcs' parameter and sum of result array must match the 'price' parameter. If there is no possible result return empty array ([]).

Help Me. I can't find a pattern

Answer 1

It is not a trivial question but can be solved by recursing.

To get the 4x10000 in the first example, we would have to optimise for same denominations or simplest set of denominations. Likely needing a two pass.

const denominations = [100000, 50000, 20000, 10000, 5000, 2000, 1000];

const  findDenominations = (price, pcs, denominations, start = 0) => {
  // Base case: if price is 0 and pcs is 0, return an empty array (successful end)
  if (price === 0 && pcs === 0) return [];
  // If price or pcs becomes negative or if we've run out of denominations, return null (failure)
  if (price < 0 || pcs < 0 || start >= denominations.length) return null;

  // Try including the current denomination
  let withCurrent = findDenominations(price - denominations[start], pcs - 1, denominations, start);
  if (withCurrent !== null) {
    return [denominations[start], ...withCurrent];
  }
  // Try excluding the current denomination 
  let withoutCurrent = findDenominations(price, pcs, denominations, start + 1); 
  return withoutCurrent;
};

const distributeDenominations = (price, pcs) => findDenominations(price, pcs, denominations) || [];

console.log(distributeDenominations(40000, 4)); // [10000, 10000, 10000, 10000] or in this case [20000, 10000, 5000, 5000]
console.log(distributeDenominations(10000, 4)); // [5000, 2000, 2000, 1000]
console.log(distributeDenominations(40000, 2)); // [20000, 20000]
console.log(distributeDenominations(50000, 2)); // []

We have two paths:

Try including the current denomination: Subtract the value of the current denomination from price and reducing pcs by 1. We keep the start index the same, allowing the same denomination to be used again. If this recursive call finds a valid combination (not null), it adds the current denomination to the front of the result (withCurrent) and returns this array.

Try excluding the current denomination: If the current denomination does not give a valid combination, the function makes another recursive call, this time keeping price and pcs the same but incrementing start by 1 to try the next denomination in the array. The result of this call (withoutCurrent) is returned.

The recursion stops when the subtractions give a negative result or we run out of denominations to try (failure) OR stops when we reach 0 on both price and pcs (success)