Count the minimum number of elements required to given sum
Here given code implementation process.
// C program
// Count the minimum number of elements required to given sum
#include <stdio.h>
// Returns the minimum value of two numbers
int minimum(int a, int b)
{
if (a < b)
{
return a;
}
else
{
return b;
}
}
// Handles the request of count minimum elements
// Sum of array elements which is equal to given sum
void countElements(int arr[], int n, int sum)
{
if (sum > 0)
{
// Auxiliary space
int dp[n + 1][sum + 1];
// Loop controlling variables
int i = 0;
int j = 0;
int element = 0;
// Set default value
for (i = 0; i <= n; ++i)
{
for (j = 0; j <= sum; ++j)
{
if (i == 0)
{
// Set first row elements
dp[i][j] = sum + 1;
}
else
{
dp[i][j] = 0;
}
}
}
// Calculate result
// Execute loop through by array size
for (i = 1; i <= n; i++)
{
// Get element
element = arr[i - 1];
if (element > 0)
{
for (j = 1; j <= sum; ++j)
{
if (element > j)
{
// When array element is greater than given sum
dp[i][j] = dp[i - 1][j];
}
else
{
// When array elements less than given sum
dp[i][j] = minimum(dp[i - 1][j], dp[i][j - element] + 1);
}
}
}
}
// Display given sum
printf("\n Given Sum : %d", sum);
if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
{
printf("\n None \n");
}
else
{
printf("\n Element : %d\n", dp[n][sum]);
}
}
}
int main()
{
// Define array of positive integers
int arr[] = {
4 , 6 , 2 , 8 , 5
};
int n = sizeof(arr) / sizeof(arr[0]);
// 31 = 8 + 8 + 8 + 5 + 2
countElements(arr, n, 31);
// 17 = 6 + 6 + 5
countElements(arr, n, 17);
countElements(arr, n, 3);
return 0;
}
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
/*
Java Program
Count the minimum number of elements required to given sum
*/
public class Counting
{
// Returns the minimum value of two numbers
public int minimum(int a, int b)
{
if (a < b)
{
return a;
}
else
{
return b;
}
}
// Handles the request of count minimum elements
// Sum of array elements which is equal to given sum
public void countElements(int[] arr, int n, int sum)
{
if (sum > 0)
{
// Auxiliary space
int[][] dp = new int[n + 1][sum + 1];
// Loop controlling variables
int i = 0;
int j = 0;
int element = 0;
// Set default value
for (i = 0; i <= n; ++i)
{
for (j = 0; j <= sum; ++j)
{
if (i == 0)
{
// Set first row elements
dp[i][j] = sum + 1;
}
else
{
dp[i][j] = 0;
}
}
}
// Calculate result
// Execute loop through by array size
for (i = 1; i <= n; i++)
{
// Get element
element = arr[i - 1];
if (element > 0)
{
for (j = 1; j <= sum; ++j)
{
if (element > j)
{
// When array element is greater than given sum
dp[i][j] = dp[i - 1][j];
}
else
{
// When array elements less than given sum
dp[i][j] = minimum(dp[i - 1][j], dp[i][j - element] + 1);
}
}
}
}
// Display given sum
System.out.print("\n Given Sum : " + sum);
if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
{
System.out.print("\n None \n");
}
else
{
System.out.println("\n Element : " + dp[n][sum]);
}
}
}
public static void main(String[] args)
{
Counting task = new Counting();
// Define array of positive integers
int[] arr = {
4 , 6 , 2 , 8 , 5
};
int n = arr.length;
// 31 = 8 + 8 + 8 + 5 + 2
task.countElements(arr, n, 31);
// 17 = 6 + 6 + 5
task.countElements(arr, n, 17);
task.countElements(arr, n, 3);
}
}
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Count the minimum number of elements required to given sum
*/
class Counting
{
public:
// Returns the minimum value of two numbers
int minimum(int a, int b)
{
if (a < b)
{
return a;
}
else
{
return b;
}
}
// Handles the request of count minimum elements
// Sum of array elements which is equal to given sum
void countElements(int arr[], int n, int sum)
{
if (sum > 0)
{
// Auxiliary space
int dp[n + 1][sum + 1];
// Loop controlling variables
int i = 0;
int j = 0;
int element = 0;
// Set default value
for (i = 0; i <= n; ++i)
{
for (j = 0; j <= sum; ++j)
{
if (i == 0)
{
// Set first row elements
dp[i][j] = sum + 1;
}
else
{
dp[i][j] = 0;
}
}
}
// Calculate result
// Execute loop through by array size
for (i = 1; i <= n; i++)
{
// Get element
element = arr[i - 1];
if (element > 0)
{
for (j = 1; j <= sum; ++j)
{
if (element > j)
{
// When array element is greater than given sum
dp[i][j] = dp[i - 1][j];
}
else
{
// When array elements less than given sum
dp[i][j] = this->minimum(dp[i - 1][j],
dp[i][j - element] + 1);
}
}
}
}
// Display given sum
cout << "\n Given Sum : " << sum;
if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
{
cout << "\n None \n";
}
else
{
cout << "\n Element : " << dp[n][sum] << endl;
}
}
}
};
int main()
{
Counting *task = new Counting();
// Define array of positive integers
int arr[] = {
4 , 6 , 2 , 8 , 5
};
int n = sizeof(arr) / sizeof(arr[0]);
// 31 = 8 + 8 + 8 + 5 + 2
task->countElements(arr, n, 31);
// 17 = 6 + 6 + 5
task->countElements(arr, n, 17);
task->countElements(arr, n, 3);
return 0;
}
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
// Include namespace system
using System;
/*
Csharp Program
Count the minimum number of elements required to given sum
*/
public class Counting
{
// Returns the minimum value of two numbers
public int minimum(int a, int b)
{
if (a < b)
{
return a;
}
else
{
return b;
}
}
// Handles the request of count minimum elements
// Sum of array elements which is equal to given sum
public void countElements(int[] arr, int n, int sum)
{
if (sum > 0)
{
// Auxiliary space
int[,] dp = new int[n + 1,sum + 1];
// Loop controlling variables
int i = 0;
int j = 0;
int element = 0;
// Set default value
for (i = 0; i <= n; ++i)
{
for (j = 0; j <= sum; ++j)
{
if (i == 0)
{
// Set first row elements
dp[i,j] = sum + 1;
}
else
{
dp[i,j] = 0;
}
}
}
// Calculate result
// Execute loop through by array size
for (i = 1; i <= n; i++)
{
// Get element
element = arr[i - 1];
if (element > 0)
{
for (j = 1; j <= sum; ++j)
{
if (element > j)
{
// When array element is greater than given sum
dp[i,j] = dp[i - 1,j];
}
else
{
// When array elements less than given sum
dp[i,j] = this.minimum(dp[i - 1,j], dp[i,j - element] + 1);
}
}
}
}
// Display given sum
Console.Write("\n Given Sum : " + sum);
if (dp[n,sum] == sum + 1 || dp[n,sum] == 0)
{
Console.Write("\n None \n");
}
else
{
Console.WriteLine("\n Element : " + dp[n,sum]);
}
}
}
public static void Main(String[] args)
{
Counting task = new Counting();
// Define array of positive integers
int[] arr = {
4 , 6 , 2 , 8 , 5
};
int n = arr.Length;
// 31 = 8 + 8 + 8 + 5 + 2
task.countElements(arr, n, 31);
// 17 = 6 + 6 + 5
task.countElements(arr, n, 17);
task.countElements(arr, n, 3);
}
}
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
<?php
/*
Php Program
Count the minimum number of elements required to given sum
*/
class Counting
{
// Returns the minimum value of two numbers
public function minimum($a, $b)
{
if ($a < $b)
{
return $a;
}
else
{
return $b;
}
}
// Handles the request of count minimum elements
// Sum of array elements which is equal to given sum
public function countElements($arr, $n, $sum)
{
if ($sum > 0)
{
// Auxiliary space
$dp = array_fill(0, $sum + 1, array_fill(0, $n + 1, 0));
// Loop controlling variables
$i = 0;
$j = 0;
$element = 0;
// Set default value
for ($i = 0; $i <= $n; ++$i)
{
for ($j = 0; $j <= $sum; ++$j)
{
if ($i == 0)
{
// Set first row elements
$dp[$i][$j] = $sum + 1;
}
else
{
$dp[$i][$j] = 0;
}
}
}
// Calculate result
// Execute loop through by array size
for ($i = 1; $i <= $n; $i++)
{
// Get element
$element = $arr[$i - 1];
if ($element > 0)
{
for ($j = 1; $j <= $sum; ++$j)
{
if ($element > $j)
{
// When array element is greater than given sum
$dp[$i][$j] = $dp[$i - 1][$j];
}
else
{
// When array elements less than given sum
$dp[$i][$j] = $this->minimum($dp[$i - 1][$j], $dp[$i][$j - $element] + 1);
}
}
}
}
// Display given sum
echo("\n Given Sum : ".$sum);
if ($dp[$n][$sum] == $sum + 1 || $dp[$n][$sum] == 0)
{
echo("\n None \n");
}
else
{
echo("\n Element : ".$dp[$n][$sum].
"\n");
}
}
}
}
function main()
{
$task = new Counting();
// Define array of positive integers
$arr = array(4, 6, 2, 8, 5);
$n = count($arr);
// 31 = 8 + 8 + 8 + 5 + 2
$task->countElements($arr, $n, 31);
// 17 = 6 + 6 + 5
$task->countElements($arr, $n, 17);
$task->countElements($arr, $n, 3);
}
main();
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
/*
Node JS Program
Count the minimum number of elements required to given sum
*/
class Counting
{
// Returns the minimum value of two numbers
minimum(a, b)
{
if (a < b)
{
return a;
}
else
{
return b;
}
}
// Handles the request of count minimum elements
// Sum of array elements which is equal to given sum
countElements(arr, n, sum)
{
if (sum > 0)
{
// Auxiliary space
var dp = Array(n + 1).fill(0).map(() => new Array(sum + 1).fill(0));
// Loop controlling variables
var i = 0;
var j = 0;
var element = 0;
// Set default value
for (i = 0; i <= n; ++i)
{
for (j = 0; j <= sum; ++j)
{
if (i == 0)
{
// Set first row elements
dp[i][j] = sum + 1;
}
else
{
dp[i][j] = 0;
}
}
}
// Calculate result
// Execute loop through by array size
for (i = 1; i <= n; i++)
{
// Get element
element = arr[i - 1];
if (element > 0)
{
for (j = 1; j <= sum; ++j)
{
if (element > j)
{
// When array element is greater than given sum
dp[i][j] = dp[i - 1][j];
}
else
{
// When array elements less than given sum
dp[i][j] = this.minimum(dp[i - 1][j], dp[i][j - element] + 1);
}
}
}
}
// Display given sum
process.stdout.write("\n Given Sum : " + sum);
if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
{
process.stdout.write("\n None \n");
}
else
{
console.log("\n Element : " + dp[n][sum]);
}
}
}
}
function main()
{
var task = new Counting();
// Define array of positive integers
var arr = [4, 6, 2, 8, 5];
var n = arr.length;
// 31 = 8 + 8 + 8 + 5 + 2
task.countElements(arr, n, 31);
// 17 = 6 + 6 + 5
task.countElements(arr, n, 17);
task.countElements(arr, n, 3);
}
main();
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
# Python 3 Program
# Count the minimum number of elements required to given sum
class Counting :
# Returns the minimum value of two numbers
def minimum(self, a, b) :
if (a < b) :
return a
else :
return b
# Handles the request of count minimum elements
# Sum of list elements which is equal to given sum
def countElements(self, arr, n, sum) :
if (sum > 0) :
dp = [[0] * (sum + 1) for _ in range(n + 1) ]
i = 0
j = 0
element = 0
# Set default value
i = 0
while (i <= n) :
j = 0
while (j <= sum) :
if (i == 0) :
# Set first row elements
dp[i][j] = sum + 1
else :
dp[i][j] = 0
j += 1
i += 1
i = 1
# Calculate result
# Execute loop through by list size
while (i <= n) :
# Get element
element = arr[i - 1]
if (element > 0) :
j = 1
while (j <= sum) :
if (element > j) :
# When list element is greater than given sum
dp[i][j] = dp[i - 1][j]
else :
# When list elements less than given sum
dp[i][j] = self.minimum(dp[i - 1][j],
dp[i][j - element] + 1)
j += 1
i += 1
# Display given sum
print("\n Given Sum : ", sum, end = "")
if (dp[n][sum] == sum + 1 or dp[n][sum] == 0) :
print("\n None ")
else :
print("\n Element : ", dp[n][sum])
def main() :
task = Counting()
arr = [4, 6, 2, 8, 5]
n = len(arr)
# 31 = 8 + 8 + 8 + 5 + 2
task.countElements(arr, n, 31)
# 17 = 6 + 6 + 5
task.countElements(arr, n, 17)
task.countElements(arr, n, 3)
if __name__ == "__main__": main()
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
# Ruby Program
# Count the minimum number of elements required to given sum
class Counting
# Returns the minimum value of two numbers
def minimum(a, b)
if (a < b)
return a
else
return b
end
end
# Handles the request of count minimum elements
# Sum of array elements which is equal to given sum
def countElements(arr, n, sum)
if (sum > 0)
# Auxiliary space
dp = Array.new(n + 1) {Array.new(sum + 1) {0}}
# Loop controlling variables
i = 0
j = 0
element = 0
# Set default value
i = 0
while (i <= n)
j = 0
while (j <= sum)
if (i == 0)
# Set first row elements
dp[i][j] = sum + 1
else
dp[i][j] = 0
end
j += 1
end
i += 1
end
# Calculate result
# Execute loop through by array size
i = 1
while (i <= n)
# Get element
element = arr[i - 1]
if (element > 0)
j = 1
while (j <= sum)
if (element > j)
# When array element is greater than given sum
dp[i][j] = dp[i - 1][j]
else
# When array elements less than given sum
dp[i][j] = self.minimum(dp[i - 1][j],
dp[i][j - element] + 1)
end
j += 1
end
end
i += 1
end
# Display given sum
print("\n Given Sum : ", sum)
if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
print("\n None \n")
else
print("\n Element : ", dp[n][sum], "\n")
end
end
end
end
def main()
task = Counting.new()
# Define array of positive integers
arr = [4, 6, 2, 8, 5]
n = arr.length
# 31 = 8 + 8 + 8 + 5 + 2
task.countElements(arr, n, 31)
# 17 = 6 + 6 + 5
task.countElements(arr, n, 17)
task.countElements(arr, n, 3)
end
main()
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
/*
Scala Program
Count the minimum number of elements required to given sum
*/
class Counting()
{
// Returns the minimum value of two numbers
def minimum(a: Int, b: Int): Int = {
if (a < b)
{
return a;
}
else
{
return b;
}
}
// Handles the request of count minimum elements
// Sum of array elements which is equal to given sum
def countElements(arr: Array[Int], n: Int, sum: Int): Unit = {
if (sum > 0)
{
// Auxiliary space
var dp: Array[Array[Int]] = Array.fill[Int](n + 1, sum + 1)(0);
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var element: Int = 0;
// Set default value
i = 0;
while (i <= n)
{
j = 0;
while (j <= sum)
{
if (i == 0)
{
// Set first row elements
dp(i)(j) = sum + 1;
}
else
{
dp(i)(j) = 0;
}
j += 1;
}
i += 1;
}
// Calculate result
// Execute loop through by array size
i = 1;
while (i <= n)
{
// Get element
element = arr(i - 1);
if (element > 0)
{
j = 1;
while (j <= sum)
{
if (element > j)
{
// When array element is greater than given sum
dp(i)(j) = dp(i - 1)(j);
}
else
{
// When array elements less than given sum
dp(i)(j) = minimum(dp(i - 1)(j), dp(i)(j - element) + 1);
}
j += 1;
}
}
i += 1;
}
// Display given sum
print("\n Given Sum : " + sum);
if (dp(n)(sum) == sum + 1 || dp(n)(sum) == 0)
{
print("\n None \n");
}
else
{
println("\n Element : " + dp(n)(sum));
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Counting = new Counting();
// Define array of positive integers
var arr: Array[Int] = Array(4, 6, 2, 8, 5);
var n: Int = arr.length;
// 31 = 8 + 8 + 8 + 5 + 2
task.countElements(arr, n, 31);
// 17 = 6 + 6 + 5
task.countElements(arr, n, 17);
task.countElements(arr, n, 3);
}
}
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
/*
Swift 4 Program
Count the minimum number of elements required to given sum
*/
class Counting
{
// Returns the minimum value of two numbers
func minimum(_ a: Int, _ b: Int)->Int
{
if (a < b)
{
return a;
}
else
{
return b;
}
}
// Handles the request of count minimum elements
// Sum of array elements which is equal to given sum
func countElements(_ arr: [Int], _ n: Int, _ sum: Int)
{
if (sum > 0)
{
// Auxiliary space
var dp: [[Int]] = Array(repeating: Array(repeating: 0,
count: sum + 1), count: n + 1);
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var element: Int = 0;
// Set default value
i = 0;
while (i <= n)
{
j = 0;
while (j <= sum)
{
if (i == 0)
{
// Set first row elements
dp[i][j] = sum + 1;
}
else
{
dp[i][j] = 0;
}
j += 1;
}
i += 1;
}
// Calculate result
// Execute loop through by array size
i = 1;
while (i <= n)
{
// Get element
element = arr[i - 1];
if (element > 0)
{
j = 1;
while (j <= sum)
{
if (element > j)
{
// When array element is greater than given sum
dp[i][j] = dp[i - 1][j];
}
else
{
// When array elements less than given sum
dp[i][j] = self.minimum(dp[i - 1][j], dp[i][j - element] + 1);
}
j += 1;
}
}
i += 1;
}
// Display given sum
print("\n Given Sum : ", sum, terminator: "");
if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
{
print("\n None ");
}
else
{
print("\n Element : ", dp[n][sum]);
}
}
}
}
func main()
{
let task: Counting = Counting();
// Define array of positive integers
let arr: [Int] = [4, 6, 2, 8, 5];
let n: Int = arr.count;
// 31 = 8 + 8 + 8 + 5 + 2
task.countElements(arr, n, 31);
// 17 = 6 + 6 + 5
task.countElements(arr, n, 17);
task.countElements(arr, n, 3);
}
main();
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
/*
Kotlin Program
Count the minimum number of elements required to given sum
*/
class Counting
{
// Returns the minimum value of two numbers
fun minimum(a: Int, b: Int): Int
{
if (a < b)
{
return a;
}
else
{
return b;
}
}
// Handles the request of count minimum elements
// Sum of array elements which is equal to given sum
fun countElements(arr: Array < Int > , n: Int, sum: Int): Unit
{
if (sum > 0)
{
// Auxiliary space
val dp: Array < Array < Int >> = Array(n + 1)
{
Array(sum + 1)
{
0
}
};
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var element: Int ;
// Set default value
while (i <= n)
{
while (j <= sum)
{
if (i == 0)
{
// Set first row elements
dp[i][j] = sum + 1;
}
else
{
dp[i][j] = 0;
}
j += 1;
}
i += 1;
j = 0;
}
// Calculate result
// Execute loop through by array size
i = 1;
while (i <= n)
{
// Get element
element = arr[i - 1];
if (element > 0)
{
j = 1;
while (j <= sum)
{
if (element > j)
{
// When array element is greater than given sum
dp[i][j] = dp[i - 1][j];
}
else
{
// When array elements less than given sum
dp[i][j] = this.minimum(dp[i - 1][j],
dp[i][j - element] + 1);
}
j += 1;
}
}
i += 1;
}
// Display given sum
print("\n Given Sum : " + sum);
if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
{
print("\n None \n");
}
else
{
println("\n Element : " + dp[n][sum]);
}
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Counting = Counting();
// Define array of positive integers
val arr: Array < Int > = arrayOf(4, 6, 2, 8, 5);
val n: Int = arr.count();
// 31 = 8 + 8 + 8 + 5 + 2
task.countElements(arr, n, 31);
// 17 = 6 + 6 + 5
task.countElements(arr, n, 17);
task.countElements(arr, n, 3);
}
input
Given Sum : 31
Element : 5
Given Sum : 17
Element : 3
Given Sum : 3
None
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