CODEWITHSUNDEEP
javascriptalgorithm
nitte93
nitte93

Reputation: 1840

Convert a number into sum of two other numbers so the difference is minimum

In Mars, there are only two denominations of currency ,x and y. A Marsian goes to a bar and the bill is "z". Using x and y he has to pay the bill. But the bar doesn't tender change, any extra money will be taken as tips.

So write a function in JavaScript that helps the marsian to reduce the tips.

The function takes in x, y, z and returns the amount of tip he has to pay.

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

Solution: I think this is level one DP problem, something like subset sum. Like for finding the optimal tip for the larger number, knowing the optimal tip for all the below numbers would help.

const coinA = 2
const coinB = 5
const sum = 13

var arr = [];
arr[0] =0;
console.log(getMyTip(coinA, coinB, sum));
function getMyTip(){
    for(var i=1; i<= sum; i++){
        var minA, minB;
        if( i < coinA){
          minA = coinA - i;
        }else{
          minA = arr[i - coinA];
        }
        if( i < coinB){
         minB = coinB - i;
        }else{
         minB = arr [i - coinB]
        }
        arr[i] = Math.min(minA, minB);
    }
    return arr[sum];

}

Jsfiddle: https://jsfiddle.net/7c4sbe46/

But I'm not sure why it is not getting accepted. Please let me know if I'm missing something with the logic here.

Upvotes: 1

Views: 522

Answers (4)

Anshul Bansal
Anshul Bansal

Reputation: 1893

var findTip = function(x=2, y=5, z=13){
var x = x;
var y = y; 
var z = z;
var tip ;
var temp1 = x;
var temp2 = y
function findNumber(num,total){
  if(num > total){
    return num-total;
   }
   else{
     var q = Math.floor(total/num);
     return ((q+1)*num)-total;
   }
}
function findMin(a,b,c){
  var min ;
  if(a<b && a<c){
    min = a
  }else{
    if(b<c){
      min = b;
    }else{
      min = c;
    }
  }
  return min;
}
while(temp1!=temp2)
{
    if(temp1 > temp2)
        temp1 -= temp2;
    else
        temp2 -= temp1;
}
var factor =temp1;
if(z%x == 0 || z%y == 0 || z%(x+y) == 0) {
  tip = 0;
}else if(z%factor == 0 && z>=x*y - x -y){
  tip = 0;
}
else {
  var minX= findNumber(x,z);
  var minY = findNumber(y,z);
  var minXY = findNumber(x+y,z);
  console.log(minX,minY,minXY)
  tip = findMin(minX,minY,minXY);
}
alert('the tip is '+ tip.toString());
return tip;
}
findTip(21, 11, 109);

Upvotes: 0

Sushil Kumar
Sushil Kumar

Reputation: 169

There is no need to use dp for this. Here is the simple solution - 

// x -> first currency denomination
// y -> second currency denomination
// z -> total bill

var calculateTip = function(x,y,z) {
  var xMax = Math.floor(z/x);
  var tip = y;
  if(xMax == 0) {
    tip = (x-z) < (Math.ceil(z/y)*y - z) ? (x-z) : (Math.ceil(z/y)*y - z);
  }
  while (xMax>=0) {
    var tempTip = xMax*x + Math.ceil((z-xMax*x)/y)*y - z;
    if(tempTip < tip) {
        tip = tempTip;
    }
    xMax--;
  }
  return tip;
}



var minimumTip = function(x,y,z) {
  if(x>y) { 
    return calculateTip(x,y,z);     
  } else {
    return calculateTip(y,x,z);
  }
}

console.log(minimumTip(2, 5, 109));

Upvotes: 0

Aditya Chandrayan
Aditya Chandrayan

Reputation: 133

#include <stdio.h>
int main()
{
int curr1, curr2, bill;

scanf("%d %d %d",&curr1,&curr2,&bill);

int gcd, tip=0;
int x=curr1;
int y=curr2;
while(x!=y)
{
    if(x > y)
        x -= y;
    else
        y -= x;
}
gcd=x;

 if((bill%curr1==0) || (bill%curr2==0) || (bill%(curr1 + curr2)==0)){
   tip = 0;  
 } else if(bill>(curr1 + curr2) && (bill % gcd==0)) {
   tip = 0;
 } else if((curr1 + curr2) > bill){
     if(curr2 > curr1){
          tip = (bill % (curr2-curr1));
     }else{
          tip = (bill % (curr1-curr2));     
     }
 }
 printf("%d",tip);
 return 0;
}

Upvotes: 0

Damien Prot
Damien Prot

Reputation: 593

It is more related to diophantine equations, i.e. is there a solution to a.x+b.y=z ? The answer is yes if z is a multiple of the greatest common divisor of x and y (called it gcd). If not, your tip will be the difference between 1. the smaller number divisible by gcd and greater than z and 2. z. Once you know the value of the tip, you can even easily know the number of x and y that you need by slightly modifying the value of z to (z+tip).

Upvotes: 1

Related Questions