Greedy algorithm to find minimum number of coins

Here given code implementation process.

import java.util.Arrays;
import java.util.Vector;
/*
    Java program
    Greedy algorithm to find minimum number of coins
*/
public class Change
{
	public void minNoOfCoins(int coins[], int n, int value)
	{
		if (value <= 0)
		{
			return;
		}
      	// Sort the given coins
		Arrays.sort(coins);
		// Use to collect coins
		Vector < Integer > record = new Vector < Integer > ();
		// Auxiliary variables
		int sum = 0;
		int i = n - 1;
		int c = 0;
		//  Find the change coins by given value
		while (i >= 0 && sum < value)
		{
			// Get coin
			c = coins[i];
			while (c + sum <= value)
			{
				// Add coin
				record.add(c);
				// Update sum
				sum += c;
			}
			// Reduce position of element
			i--;
		}
		System.out.println("\n Given value is " + value);
		if (sum == value)
		{
			// When change are possible.  
			// Display resultant coins.
			for (int v = 0; v < record.size(); ++v)
			{
				System.out.print("  " + record.get(v));
			}
		}
		else
		{
			System.out.print(" Full change are not possible \n");
		}
	}
	public static void main(String[] args)
	{
		Change task = new Change();
		int[] coins = {
			6 , 1 , 5 , 2 , 10
		};
		int n = coins.length;
		// Value = 52
		task.minNoOfCoins(coins, n, 52);
		// Value = 38
		task.minNoOfCoins(coins, n, 38);
		// Value = 7
		task.minNoOfCoins(coins, n, 7);
	}
}

Output

 Given value is 52
  10  10  10  10  10  2
 Given value is 38
  10  10  10  6  2
 Given value is 7
  6  1
// Include header file
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
/*
    C++ program
    Greedy algorithm to find minimum number of coins
*/
class Change
{
	public: void minNoOfCoins(int coins[], int n, int value)
	{
		if (value <= 0)
		{
			return;
		}
		// Sort the given coins
		sort(coins, coins + n);
		// Use to collect coins
		vector < int > record;
		// Auxiliary variables
		int sum = 0;
		int i = n - 1;
		int c = 0;
		//  Find the change coins by given value
		while (i >= 0 && sum < value)
		{
			// Get coin
			c = coins[i];
			while (c + sum <= value)
			{
				// Add coin
				record.push_back(c);
				// Update sum
				sum += c;
			}
			// Reduce position of element
			i--;
		}
		cout << "\n Given value is " << value << endl;
		if (sum == value)
		{
			// When change are possible.  
			// Display resultant coins.
			for (int v = 0; v < record.size(); ++v)
			{
				cout << "  " << record.at(v);
			}
		}
		else
		{
			cout << " Full change are not possible \n";
		}
	}
};
int main()
{
	Change *task = new Change();
	int coins[] = {
		6 , 1 , 5 , 2 , 10
	};
	int n = sizeof(coins) / sizeof(coins[0]);
	// Value = 52
	task->minNoOfCoins(coins, n, 52);
	// Value = 38
	task->minNoOfCoins(coins, n, 38);
	// Value = 7
	task->minNoOfCoins(coins, n, 7);
	return 0;
}

Output

 Given value is 52
  10  10  10  10  10  2
 Given value is 38
  10  10  10  6  2
 Given value is 7
  6  1
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp program
    Greedy algorithm to find minimum number of coins
*/
public class Change
{
	public void minNoOfCoins(int[] coins, int n, int value)
	{
		if (value <= 0)
		{
			return;
		}
		// Sort the given coins
		Array.Sort(coins);
		// Use to collect coins
		List < int > record = new List < int > ();
		// Auxiliary variables
		int sum = 0;
		int i = n - 1;
		int c = 0;
		//  Find the change coins by given value
		while (i >= 0 && sum < value)
		{
			// Get coin
			c = coins[i];
			while (c + sum <= value)
			{
				// Add coin
				record.Add(c);
				// Update sum
				sum += c;
			}
			// Reduce position of element
			i--;
		}
		Console.WriteLine("\n Given value is " + value);
		if (sum == value)
		{
			// When change are possible.  
			// Display resultant coins.
			for (int v = 0; v < record.Count; ++v)
			{
				Console.Write("  " + record[v]);
			}
		}
		else
		{
			Console.Write(" Full change are not possible \n");
		}
	}
	public static void Main(String[] args)
	{
		Change task = new Change();
		int[] coins = {
			6 , 1 , 5 , 2 , 10
		};
		int n = coins.Length;
		// Value = 52
		task.minNoOfCoins(coins, n, 52);
		// Value = 38
		task.minNoOfCoins(coins, n, 38);
		// Value = 7
		task.minNoOfCoins(coins, n, 7);
	}
}

Output

 Given value is 52
  10  10  10  10  10  2
 Given value is 38
  10  10  10  6  2
 Given value is 7
  6  1
package main
import "sort"
import "fmt"
/*
    Go program
    Greedy algorithm to find minimum number of coins
*/
type Change struct {}
func getChange() * Change {
	var me *Change = &Change {}
	return me
}
func(this Change) minNoOfCoins(coins[] int, n int, value int) {
	if value <= 0 {
		return
	}
	// Sort the given coins
	sort.Ints(coins)
	// Use to collect coins
	var record = make([]int,0)
	// Auxiliary variables
	var sum int = 0
	var i int = n - 1
	var c int = 0
	//  Find the change coins by given value
	for (i >= 0 && sum < value) {
		// Get coin
		c = coins[i]
		for (c + sum <= value) {
			// Add coin
			record = append(record, c)
			// Update sum
			sum += c
		}
		// Reduce position of element
		i--
	}
	fmt.Println("\n Given value is ", value)
	if sum == value {
		// When change are possible.  
		// Display resultant coins.
		for v := 0 ; v < len(record) ; v++ {
			fmt.Print("  ", record[v])
		}
	} else {
		fmt.Print(" Full change are not possible \n")
	}
}
func main() {
	var task * Change = getChange()
	var coins = [] int {
		6,
		1,
		5,
		2,
		10,
	}
	var n int = len(coins)
	// Value = 52
	task.minNoOfCoins(coins, n, 52)
	// Value = 38
	task.minNoOfCoins(coins, n, 38)
	// Value = 7
	task.minNoOfCoins(coins, n, 7)
}

Output

 Given value is 52
  10  10  10  10  10  2
 Given value is 38
  10  10  10  6  2
 Given value is 7
  6  1
<?php
/*
    Php program
    Greedy algorithm to find minimum number of coins
*/
class Change
{
	public	function minNoOfCoins($coins, $n, $value)
	{
		if ($value <= 0)
		{
			return;
		}
		// Sort the given coins
		sort($coins);
		// Use to collect coins
		$record = array();
		// Auxiliary variables
		$sum = 0;
		$i = $n - 1;
		$c = 0;
		//  Find the change coins by given value
		while ($i >= 0 && $sum < $value)
		{
			// Get coin
			$c = $coins[$i];
			while ($c + $sum <= $value)
			{
				// Add coin
				$record[] = $c;
				// Update sum
				$sum += $c;
			}
			// Reduce position of element
			$i--;
		}
		echo("\n Given value is ".$value.
			"\n");
		if ($sum == $value)
		{
			// When change are possible.  
			// Display resultant coins.
			for ($v = 0; $v < count($record); ++$v)
			{
				echo("  ".$record[$v]);
			}
		}
		else
		{
			echo(" Full change are not possible \n");
		}
	}
}

function main()
{
	$task = new Change();
	$coins = array(6, 1, 5, 2, 10);
	$n = count($coins);
	// Value = 52
	$task->minNoOfCoins($coins, $n, 52);
	// Value = 38
	$task->minNoOfCoins($coins, $n, 38);
	// Value = 7
	$task->minNoOfCoins($coins, $n, 7);
}
main();

Output

 Given value is 52
  10  10  10  10  10  2
 Given value is 38
  10  10  10  6  2
 Given value is 7
  6  1
/*
    Node JS program
    Greedy algorithm to find minimum number of coins
*/
class Change
{
	minNoOfCoins(coins, n, value)
	{
		if (value <= 0)
		{
			return;
		}
		// Sort the given coins
		coins.sort(function(a, b)
		{
			return a - b;
		});
		// Use to collect coins
		var record = [];
		// Auxiliary variables
		var sum = 0;
		var i = n - 1;
		var c = 0;
		//  Find the change coins by given value
		while (i >= 0 && sum < value)
		{
			// Get coin
			c = coins[i];
			while (c + sum <= value)
			{
				// Add coin
				record.push(c);
				// Update sum
				sum += c;
			}
			// Reduce position of element
			i--;
		}
		console.log("\n Given value is " + value);
		if (sum == value)
		{
			// When change are possible.  
			// Display resultant coins.
			for (var v = 0; v < record.length; ++v)
			{
				process.stdout.write("  " + record[v]);
			}
		}
		else
		{
			process.stdout.write(" Full change are not possible \n");
		}
	}
}

function main()
{
	var task = new Change();
	var coins = [6, 1, 5, 2, 10];
	var n = coins.length;
	// Value = 52
	task.minNoOfCoins(coins, n, 52);
	// Value = 38
	task.minNoOfCoins(coins, n, 38);
	// Value = 7
	task.minNoOfCoins(coins, n, 7);
}
main();

Output

 Given value is 52
  10  10  10  10  10  2
 Given value is 38
  10  10  10  6  2
 Given value is 7
  6  1
#    Python 3 program
#    Greedy algorithm to find minimum number of coins
class Change :
	def minNoOfCoins(self, coins, n, value) :
		if (value <= 0) :
			return
		
		#  Sort the given coins
		coins.sort()
		#  Use to collect coins
		record = []
		#  Auxiliary variables
		sum = 0
		i = n - 1
		c = 0
		#   Find the change coins by given value
		while (i >= 0 and sum < value) :
			#  Get coin
			c = coins[i]
			while (c + sum <= value) :
				#  Add coin
				record.append(c)
				#  Update sum
				sum += c
			
			#  Reduce position of element
			i -= 1
		
		print("\n Given value is ", value)
		if (sum == value) :
			v = 0
			#  When change are possible.  
			#  Display resultant coins.
			while (v < len(record)) :
				print("  ", record[v], end = "")
				v += 1
			
		else :
			print(" Full change are not possible ")
		
	

def main() :
	task = Change()
	coins = [6, 1, 5, 2, 10]
	n = len(coins)
	#  Value = 52
	task.minNoOfCoins(coins, n, 52)
	#  Value = 38
	task.minNoOfCoins(coins, n, 38)
	#  Value = 7
	task.minNoOfCoins(coins, n, 7)

if __name__ == "__main__": main()

Output

 Given value is  52
   10   10   10   10   10   2
 Given value is  38
   10   10   10   6   2
 Given value is  7
   6   1
#    Ruby program
#    Greedy algorithm to find minimum number of coins
class Change 
	def minNoOfCoins(coins, n, value) 
		if (value <= 0) 
			return
		end

		#  Sort the given coins
		coins = coins.sort
		#  Use to collect coins
		record = []
		#  Auxiliary variables
		sum = 0
		i = n - 1
		c = 0
		#   Find the change coins by given value
		while (i >= 0 && sum < value) 
			#  Get coin
			c = coins[i]
			while (c + sum <= value) 
				#  Add coin
				record.push(c)
				#  Update sum
				sum += c
			end

			#  Reduce position of element
			i -= 1
		end

		print("\n Given value is ", value, "\n")
		if (sum == value) 
			v = 0
			#  When change are possible.  
			#  Display resultant coins.
			while (v < record.length) 
				print("  ", record[v])
				v += 1
			end

		else
 
			print(" Full change are not possible \n")
		end

	end

end

def main() 
	task = Change.new()
	coins = [6, 1, 5, 2, 10]
	n = coins.length
	#  Value = 52
	task.minNoOfCoins(coins, n, 52)
	#  Value = 38
	task.minNoOfCoins(coins, n, 38)
	#  Value = 7
	task.minNoOfCoins(coins, n, 7)
end

main()

Output

 Given value is 52
  10  10  10  10  10  2
 Given value is 38
  10  10  10  6  2
 Given value is 7
  6  1
import scala.collection.mutable._;
/*
    Scala program
    Greedy algorithm to find minimum number of coins
*/
class Change()
{
	def minNoOfCoins(collection: Array[Int], n: Int, value: Int): Unit = {
		if (value <= 0)
		{
			return;
		}
		// Sort the given coins
		val coins = collection.sorted;
		// Use to collect coins
		var record: ArrayBuffer[Int] = new ArrayBuffer[Int]();
		// Auxiliary variables
		var sum: Int = 0;
		var i: Int = n - 1;
		var c: Int = 0;
		//  Find the change coins by given value
		while (i >= 0 && sum < value)
		{
			// Get coin
			c = coins(i);
			while (c + sum <= value)
			{
				// Add coin
				record += c;
				// Update sum
				sum += c;
			}
			// Reduce position of element
			i -= 1;
		}
		println("\n Given value is " + value);
		if (sum == value)
		{
			var v: Int = 0;
			// When change are possible.  
			// Display resultant coins.
			while (v < record.size)
			{
				print("  " + record(v));
				v += 1;
			}
		}
		else
		{
			print(" Full change are not possible \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Change = new Change();
		var coins: Array[Int] = Array(6, 1, 5, 2, 10);
		var n: Int = coins.length;
		// Value = 52
		task.minNoOfCoins(coins, n, 52);
		// Value = 38
		task.minNoOfCoins(coins, n, 38);
		// Value = 7
		task.minNoOfCoins(coins, n, 7);
	}
}

Output

 Given value is 52
  10  10  10  10  10  2
 Given value is 38
  10  10  10  6  2
 Given value is 7
  6  1
import Foundation;
/*
    Swift 4 program
    Greedy algorithm to find minimum number of coins
*/
class Change
{
	func minNoOfCoins(_ collection: [Int], _ n: Int, _ value: Int)
	{
		if (value <= 0)
		{
			return;
		}
		// Sort the given coins
		let coins = collection.sorted();
		// Use to collect coins
		var record: [Int] = [Int]();
		// Auxiliary variables
		var sum: Int = 0;
		var i: Int = n - 1;
		var c: Int = 0;
		//  Find the change coins by given value
		while (i >= 0 && sum < value)
		{
			// Get coin
			c = coins[i];
			while (c + sum <= value)
			{
				// Add coin
				record.append(c);
				// Update sum
				sum += c;
			}
			// Reduce position of element
			i -= 1;
		}
		print("\n Given value is ", value);
		if (sum == value)
		{
			var v: Int = 0;
			// When change are possible.  
			// Display resultant coins.
			while (v < record.count)
			{
				print("  ", record[v], terminator: "");
				v += 1;
			}
		}
		else
		{
			print(" Full change are not possible ");
		}
	}
}
func main()
{
	let task: Change = Change();
	let coins: [Int] = [6, 1, 5, 2, 10];
	let n: Int = coins.count;
	// Value = 52
	task.minNoOfCoins(coins, n, 52);
	// Value = 38
	task.minNoOfCoins(coins, n, 38);
	// Value = 7
	task.minNoOfCoins(coins, n, 7);
}
main();

Output

 Given value is  52
   10   10   10   10   10   2
 Given value is  38
   10   10   10   6   2
 Given value is  7
   6   1
/*
    Kotlin program
    Greedy algorithm to find minimum number of coins
*/
class Change
{
	fun minNoOfCoins(coins: Array < Int > , n: Int, value: Int): Unit
	{
		if (value <= 0)
		{
			return;
		}
		// Sort the given coins
		coins.sort();
		// Use to collect coins
		val record: MutableList < Int > = mutableListOf < Int > ();
		// Auxiliary variables
		var sum: Int = 0;
		var i: Int = n - 1;
		var c: Int ;
		//  Find the change coins by given value
		while (i >= 0 && sum < value)
		{
			// Get coin
			c = coins[i];
			while (c + sum <= value)
			{
				// Add coin
				record.add(c);
				// Update sum
				sum += c;
			}
			// Reduce position of element
			i -= 1;
		}
		println("\n Given value is " + value);
		if (sum == value)
		{
			var v: Int = 0;
			// When change are possible.  
			// Display resultant coins.
			while (v < record.size)
			{
				print("  " + record[v]);
				v += 1;
			}
		}
		else
		{
			print(" Full change are not possible \n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Change = Change();
	val coins: Array < Int > = arrayOf(6, 1, 5, 2, 10);
	val n: Int = coins.count();
	// Value = 52
	task.minNoOfCoins(coins, n, 52);
	// Value = 38
	task.minNoOfCoins(coins, n, 38);
	// Value = 7
	task.minNoOfCoins(coins, n, 7);
}

Output

 Given value is 52
  10  10  10  10  10  2
 Given value is 38
  10  10  10  6  2
 Given value is 7
  6  1


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment




© 2021, kalkicode.com, All rights reserved