Posted on by Kalkicode
Code Dynamic Programming

# Count the minimum number of elements required to given sum

In this article, we will discuss the problem of counting the minimum number of elements required to achieve a given sum. We'll provide a step-by-step explanation of the algorithm and include the pseudocode for better understanding. Additionally, we'll explain the output of the provided code examples along with their time complexity analysis.

## Problem Statement

Given an array of positive integers and a target sum, we need to find the minimum number of elements from the array whose sum is equal to the given target sum.

## Pseudocode Algorithm

```countElements(arr[], n, sum):
dp[][]     // auxiliary space for dynamic programming
initialize dp[][] with default values

for i = 1 to n:
element = arr[i - 1]
if element > 0:
for j = 1 to sum:
if element > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = minimum(dp[i - 1][j], dp[i][j - element] + 1)

display given sum
if dp[n][sum] == sum + 1 or dp[n][sum] == 0:
print "None"
else:
print "Element:", dp[n][sum]
```

## Explanation

The pseudocode outlines the steps to solve the problem. We use dynamic programming to build a 2D array `dp[][]` as an auxiliary space. The array stores the minimum number of elements required to achieve the given sum at each position. We initialize it with default values.

We iterate through the array `arr[]` and calculate the minimum number of elements needed for each sum. We consider two cases:

• If the current element is greater than the sum, we skip it.
• If the current element is less than or equal to the sum, we choose the minimum of two possibilities:
• Excluding the current element: `dp[i - 1][j]`
• Including the current element: `dp[i][j - element] + 1`

After calculating all possible sums, we check the value at `dp[n][sum]` (where `n` is the size of the array). If it is either `sum + 1` or `0`, it means no combination of elements exists to achieve the given sum. Otherwise, we display the minimum number of elements required.

## Code Solution

``````// 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)
{
// Define array of positive integers
int[] arr = {
4 , 6 , 2 , 8 , 5
};
int n = arr.length;
// 31 = 8 + 8 + 8 + 5 + 2
// 17 = 6 + 6 + 5
}
}``````

#### 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()
{
// 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
// 17 = 6 + 6 + 5
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)
{
// Define array of positive integers
int[] arr = {
4 , 6 , 2 , 8 , 5
};
int n = arr.Length;
// 31 = 8 + 8 + 8 + 5 + 2
// 17 = 6 + 6 + 5
}
}``````

#### 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()
{
// Define array of positive integers
\$arr = array(4, 6, 2, 8, 5);
\$n = count(\$arr);
// 31 = 8 + 8 + 8 + 5 + 2
// 17 = 6 + 6 + 5
}
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()
{
// Define array of positive integers
var arr = [4, 6, 2, 8, 5];
var n = arr.length;
// 31 = 8 + 8 + 8 + 5 + 2
// 17 = 6 + 6 + 5
}
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() :
arr = [4, 6, 2, 8, 5]
n = len(arr)
#  31 = 8 + 8 + 8 + 5 + 2
#  17 = 6 + 6 + 5

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()
#  Define array of positive integers
arr = [4, 6, 2, 8, 5]
n = arr.length
#  31 = 8 + 8 + 8 + 5 + 2
#  17 = 6 + 6 + 5
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
// 17 = 6 + 6 + 5
}
}``````

#### 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()
{
// Define array of positive integers
let arr: [Int] = [4, 6, 2, 8, 5];
let n: Int = arr.count;
// 31 = 8 + 8 + 8 + 5 + 2
// 17 = 6 + 6 + 5
}
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
{
// 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
// 17 = 6 + 6 + 5
}``````

#### input

`````` Given Sum : 31
Element : 5

Given Sum : 17
Element : 3

Given Sum : 3
None``````

## Resultant Output Explanation

We'll now explain the output of the provided code examples:

Given Sum Result
31 Element: 5
17 Element: 3
3 None

The first example uses a given sum of 31. From the provided array, we can obtain 31 using the elements [8, 8, 8, 5, 2]. The minimum number of elements required is 5.

In the second example, the given sum is 17. We can achieve this using the elements [6, 6, 5]. Thus, the minimum number of elements required is 3.

For the third example, the given sum is 3. There is no combination of elements from the array that can add up to 3. Hence, the result is "None."

## Time Complexity

The time complexity of the provided algorithm is `O(n * sum)` since we have a nested loop iterating over `n` and `sum` elements. In the worst case, the algorithm will iterate over all elements and calculate the minimum for each sum. However, the space complexity is `O(n * sum)` as well due to the need for the auxiliary 2D array.

In conclusion, the algorithm efficiently solves the problem of counting the minimum number of elements required to achieve a given sum. It utilizes dynamic programming to find the optimal solution. By understanding the algorithm and analyzing the output, we can solve similar problems efficiently.

## Comment

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.

Categories
Relative Post