Tag Archives: algorithms

You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .

0
Posted on by

Time complexity : O(n)

Space complexity: O(1)

We implement count sort technique to get the frequency of the elements 1 to n

[gist https://gist.github.com/vishnujayvel/5998457]

Change Making problem-Dynamic Programming

1
Posted on by

Problem:

Given a value n, if we want to make change for n cents, and we have infinite supply of each of d = { d1, d2, .. , dm} valued coins, what is the minimum number of coins to make the change?

 

#include<iostream>
using namespace std;
int d[4]={1,2,5,10};//denomination array
int k=4;//number of denomination
void getMinimumNumberOfChanges(int n){
//c[i] => array to store the minimum number of coins required to value i
//s[i] => array to store the last coin required to get the value i
int c[n],s[n],min,coin;
c[0]=0;
//DP is all about splitting in the problem into many sub problems
//here we first find no. of changes for p=1 then ,p=2 ,......till p= n which is the required value
//so first for loop runs from p=1 to n
for(int p=1;p<=n;p++){
min=999;
considering all possible denominations from array index 0 to k-1
for(int i=0;i<k;i++){
if(d[i]<=p){
if(1+c[p-d[i]]<min){
min=1+c[p-d[i]];
coin=i;
}
}
}
c[p]=min;
s[p]=coin;
}
cout<<"Minimum no. of coins required "<<c[n];
cout<<"coins are"<<'\n';
//this while loop is for tracing the coins.the code is self explanatory
while(n>0){
cout<<d[s[n]]<<"\n";
n=n-d[s[n]];
}
}
view raw changemaking.cpp hosted with ❤ by GitHub