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
- Excluding the current element:
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)
{
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
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.
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