Morgan Stanley Interview Question
Applications DevelopersCountry: India
Interview Type: Written Test
#include<iostream>
using namespace std;
int my_count(int Amount, int i, int Denomination[], int N)
{
if (Amount == 0) {
return 1;
}
if (i == N) {
return 0;
}
int n, j, result;
n = Amount / Denomination[i];
result = 0;
for (j = 0; j <= n; j++) {
result += my_count(Amount - j * Denomination[i], i + 1, Denomination, N);
}
return result;
}
int makeChange(int Amount, int Denomination[], int N)
{
return my_count(Amount, 0, Denomination, N);
}
int main(int argc, char **argv)
{
int amount;
int dem[6] = {1, 2, 5, 10, 50, 100};
cin >> amount;
cout << makeChange(amount, dem, 6) << endl;
return 0;
}
public class CombinationofCoins {
int numberoways(int den,int array[],int pos)
{
if(den<0||pos==array.length)
return 0;
if(den==0)
return 1;
int numways=0;
for(int i=pos;i<array.length;i++)
{
numways+=numberoways(den-array[i],array,i);
}
return numways;
}
public static void main(String args[])
{
int arr[]={2,3,4,5};
CombinationofCoins obj=new CombinationofCoins();
System.out.println(obj.numberoways(9, arr, 0));
}
}
public int makeChange(int Amount, int[] Denominations) {
return makeChange_using_K_and_After(Amount, Denominations, 0);
}
public int makeChange_using_K_and_After(int Amount, int[] Denominations, int K) {
if (Amount < 0 || K >= Denominations.length ||) return 0;
if (Amount == 0) return 1;
int result = 0;
for (int i = K; i < Denominations.length; i++) {
result += makeChange_using_K_and_After(Amount-Denominations[i], Denominations, i+1);
}
return result;
}
// c solution
int minCoins( int a[], int N, int S ){
/* N: Length of the array */
int i,j,n,k,val[100],total,sum;
n=N;
for(i=0;i<n;i++)
val[i]=0;
total=S;
for(i=n-1;i>=0&&total!=0;i--)
{
j=(total/a[i]);
if(j>0)
{
val[i]=j;
total=total-(j*a[i]);
}
}
sum=0;
for(i=n-1;i>=0;i--)
{
if(val[i]!=0)
{
sum=sum+val[i];
}
}
if(total!=0)
return -1;
else
return sum;
}
public class CombinationsOfDeniminations {
static int a[]={2,3,4,5};
static void print(int k,int tot)
{
if(k==a.length)
return;
int sum=0;
String newString="";
for(int i=k;i<a.length;i++)
{
sum+=a[i];
newString+=a[i]+",";
if(sum==tot)
{
System.out.println(newString);
}
}
print(k+1,tot);
}
public static void main(String[] args) {
print(0,9);
}
}
#include "stdafx.h"
- Amit Raut January 27, 2014#include <string>
#include <list>
#include <algorithm>
#include <afx.h>
#include <sstream>
using namespace std;
typedef list<int> denominations;
int Makechange(int amount, denominations& d)
{
int ways = 0;
int currentDenomination = 0;
if(amount == 0)
{
ways = 1;
}
else if(amount > 0)
{
auto it = d.begin();
while(it != d.end())
{
if((*it)!=0)
{
currentDenomination = *it;
break;
}
++it;
}
if(currentDenomination > 0)
{
int num1 = Makechange(amount-currentDenomination, d);
*it = 0;
int num2 = Makechange(amount,d);
*it = currentDenomination;
ways = num1 + num2;
}
}
return ways;
}
int _tmain(int argc, _TCHAR* argv[])
{
denominations myD;
myD.push_back(5);
myD.push_back(2);
myD.push_back(1);
int ways = Makechange(5, myD);
return 0;
}