CareerCup

// ZoomBA
def ways_to_dist( path, cur_sum , target_value ){
   if ( cur_sum > target_value ) return 0
   if ( cur_sum == target_value  ) {
      println( path )
      return 1
   }
   cnt = 0
   for ( inc : [1,5,10,25 ] ){
     if ( inc >= path[-1] ){
       cnt += ways_to_dist ( path + inc, cur_sum + inc, target_value)
     }
   }
   return cnt
}
println ( ways_to_dist( list(0), 0, 42  ) )

We tried a bit sanity here. BUT, we are not sure, we are going to optimize it further.

// ZoomBA
def ways_to_dist( target_value ){
   count = 0
   q = list() // create a queue
   q.enqueue ( [0,0,list(0)] ) // add to it
   // now the loop
   while ( !empty(q) ){
     #( prev_inc , cur_sum , path ) = q.dequeue()
     continue ( cur_sum > target_value ) // obvious, nothing else can do
     continue ( cur_sum == target_value  ) {
       println( path ) // for debug diagnostic
       count +=1 // increment possible scenarios
     }
     for ( inc : [1,5,10,25 ] ){
        if ( inc >= prev_inc ){ // ensure sorted path
           q.enqueue( [ inc , cur_sum + inc , path + inc  ] )
        }
     }
   }
   return count
}
println ( ways_to_dist( 42 ))

This is now a non recursive solution.

#include <iostream>
using namespace std;
int coin_chng(int*arr,int n,int sum,int dp[][100])
{
	if(sum==0)
		return 1;
	if(n<0)
		return 0;
	if(dp[sum][n]!=-1)
		return dp[sum][n];
	if(arr[n]>sum)
		return dp[sum][n]=coin_chng(arr,n-1,sum,dp);
	return dp[sum][n]=coin_chng(arr,n,sum-arr[n],dp)+coin_chng(arr,n-1,sum,dp);
}
int main() {
	// your code goes here
	int arr[]={1,5,10,25};
	int sum=5;
	int n=sizeof(arr)/sizeof(arr[0]);
	int dp[100][100];
	for(int i=0;i<=sum;i++)
	{
		for(int j=0;j<n;j++)
			dp[i][j]={-1};
	}
	int num=coin_chng(arr,n-1,sum,dp);
	cout<<"Possible combinations are: "<<num;
	return 0;
}

A D.P approach!(Top down approach)
Tiime complexity-O(n^2)

public class CoinDenomination {

	public static void main(String[] args) {
		double coins[] = {25.0,10.0,5.0,1.0};
		double sum = 2342.5;
		int count = 0;
		
		for(int i=0;i<coins.length;i++){
			count = (int) (sum/coins[i]);
			sum = sum - count * coins[i];
			System.out.println("Denomination for " + coins[i] + " is:" + count);
			count = 0;
		}
		
		if(sum > 0){
			System.out.println("The balance of " + sum + " have no coin denomination available");
		}
		

	}

}