CareerCup

Something like this, bit long can be done optimally using for loop:::

int main ()

{
float return_val;
float cost = 20.5;
float cash = 91;
float quat = 0.25;
float under_dollar;
int num_twenty, num_ten,num_five,num_one,num_quarter;


if (cash<cost){
printf("pay: %f", cost);
}
else {
return_val = cash-cost;

while(return_val != 0)
{
num_twenty = return_val/20;
printf("number of 20 %d \n",num_twenty);

return_val = return_val-num_twenty*20;

if (return_val/10 !=0){
num_ten = return_val/10;
return_val = return_val-num_ten*10;
printf("number of 10 %d\n",num_ten);

}

if(return_val/5 !=0){
num_five = return_val/5;
return_val = return_val - num_five*5;
printf("number of 5 %d\n",num_five);

}

if(return_val/1 !=0){
num_one = return_val;
return_val = return_val - num_one;
printf("number of 1 %d\n",num_one);

}
//printf("remaineder %f\n",return_val);
if(return_val/quat !=0){
num_quarter = return_val/quat;
return_val = return_val - num_quarter*0.25;
printf("number of quaters %d\n",num_quarter);
}
return_val = 0;
}
}



return 0;
}

void ReturnTheChange()
{
#define DENOMINATIONS 13
    // currency in cents
    int currencyDenomination[DENOMINATIONS] = {100000, 50000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5};
    int denoCount[DENOMINATIONS] = {0};
    float number;

    cin >> number;

    int input = (int)(number * 100);
    int denoIndex = 0;

    for (int remainder = input; remainder >= 5; )
    {
        while (remainder > currencyDenomination[denoIndex])
        {
            denoCount[denoIndex]++;
            remainder -= currencyDenomination[denoIndex];
        }
        denoIndex++;
    }
    float change = 0;

    for(int i = 0; i < DENOMINATIONS; ++i)
    {
        if (denoCount[i] > 0)
        {
            change += denoCount[i] * (float)currencyDenomination[i]/100;
            cout << " Need " << denoCount[i] << ", " << (float)currencyDenomination[i]/100 << "  denomination" << endl;
        }
    }

    cout << "\nTotal change is " << change << endl;

    if (number - change > 0)
        cout << number - change << "cents rounded off" << endl;

    getchar();
}

Its not greedy approach.. its DP.. Below is the algorithm

c[0]=0;
s[0]=0;

for(i=1;i<n;i++)
{
c[i] = INT_MAX;
for(j=0;j<d;j++)
{
if(i>=d[j])
{
if(c[i-d[j]]>d[j])
{
c[i] = 1+ c[i-d[j]];
s[i] = i;
}
}
}
}

at the end print the change

while(n>0)
{
print(s[n]);
n = n-s[n];
}