Least Tip Problem

leastTipProblem.js

function sortedInsert(queue, insertValue)
{
	// if queue is empty, insert value and return right away
	if (queue.length == 0) {
  	queue.push(insertValue);
    return;
  }
  
  // if last element of queue is less than insert value
  // insert at the end and return
  if (queue[queue.length-1] < insertValue) {
  	queue.push(insertValue);
    return;
  }
  
  // binary search for the position to insert the value
  var minIndex = 0;
  var maxIndex = queue.length - 1;
  var currentIndex;
  var currentElement;
  
  while (minIndex <= maxIndex) {
    currentIndex = (minIndex + maxIndex) / 2 | 0;
    currentElement = queue[currentIndex];

    if (currentElement < insertValue) {
      minIndex = currentIndex + 1;
    }
    else if (currentElement > insertValue) {
      maxIndex = currentIndex - 1;
    }
    else {
    	// insert value already exist
      return;
    }
  }
  
  var index = currentIndex;
  if (currentElement < insertValue) {
  	index = currentIndex + 1;
  }
    
  queue.splice(index, 0, insertValue);
}

function leastTip(x, y, z)
{
	// initialize min and max currencies
	minCurrency = Math.min(x, y);
  maxCurrency = Math.max(x, y);
  
  // case for negative currencies
  if (x < 0 || y < 0) {
  	return "Error. Can't have negative currency";
  }
  
  // case when currencies are higher than bill
	if (x > z && y > z) {
  	return minCurrency - z;
  }
  
  // case when currencies are same. No need for looping
  if (x == y) {
  
  	// prevent division by zero
  	if (x == 0) {
    	return "Error. Can't have both currency denominations 0 or less";
    }
    
    // get number of coins needed to pay the bill.
  	var currencyNeeded = x * Math.ceil(z/x);
    return currencyNeeded - z;
  }
  
  // initialize variables
  var hashmap = {};
  var queue = [];
  var currencies = [x, y];
  var top = z + maxCurrency;
  var minVal = top;
  var sum = 0;
  
  // loop while first element in queue is greater than top
  while (sum <= z) {
  	
    // loop over each different currency (generalized)
  	currencies.forEach(function(currency) {
    	// get new sum value by adding currency to lowest in the queue
    	var temp = sum + currency;
      
      // update min value if it's minimum
    	if (temp >= z && minVal > temp - z) {
      	minVal = temp - z;
      }
      
      // if the temp sum isn't in the hashmap, add that to queue
      if (!hashmap.hasOwnProperty(temp)) {
      	// insert added sum in queue and keep that sorted
				sortedInsert(queue, temp);
        //insert added sum to hashmap for faster lookups
        hashmap[temp] = temp;
      }
		});

    // console.log(queue);

    // remove the smallest element we have already iterated over
    sum = queue.shift();
    delete hashmap[sum];
  }
  
  // return the minimum value
  return minVal;
  
}

console.log(leastTip(2, 5, 109)); // 0
console.log(leastTip(5, 7, 43)); // 0
console.log(leastTip(15, 19, 33)); // 1
console.log(leastTip(3, 5, 7)); // 1
console.log(leastTip(1, 1, 0)); // 1
console.log(leastTip(0, 0, 0)); // Error
console.log(leastTip(0, -1, 0)); // Error
console.log(leastTip(-3, -6, 8)); // Error

LeastTipProblem.md

In a country, there are only 2 currency denominations x and y. z is the bill amount.

Write a function to minimize the amount a person has to pay as tip with the bill. As there is no denomination less than x and y, any amount paid above z is considered tip

Input: x, y, z Output: k or "Error..." (where k is the tip amount)

Example 1

Input: 2, 5, 109 Output: 0 Explanation: 21 coins of 5, and 2 coins of 2

Example 2

Input: 5, 7, 43 Output: 0 Explanation: 4 coins of 7, and 3 coins of 5

Example 3

Input: 15, 19, 33 Output: 1 Explanation: 1 coin of 15 and 1 coin of 19