C++ Exercises: Counts the number of combinations where the sum of the digits equals to given number
C++ Basic: Exercise-72 with Solution
Write a C++ program that reads n digits chosen from 0 to 9 and counts the number of combinations where the sum of the digits equals the given number. Do not use the same digits in a combination.
For example, the combinations where n = 2 and s = 5 are as follows:
0 + 5 = 5
1 + 4 = 5
3 + 2 = 5
Visual Presentation:
Sample Solution:
C++ Code :
#include <string.h> // Header file for string manipulation
#include <iostream> // Header file for input/output stream operations
using namespace std; // Using the standard namespace
int main()
{
const int MAX_NUM = 9; // Maximum number of digits
const int MAX_NOS = 9; // Maximum number of sets
const int MAX_SUM_VAL = 100; // Maximum sum value
int n, s, dp[MAX_NOS + 1][MAX_NUM + 1][MAX_SUM_VAL + 1]; // Declaration of variables and an array for dynamic programming
long long SUM_VAL = 0; // Initializing SUM_VAL as a long long variable
memset(dp, 0, sizeof(dp)); // Initializing the 'dp' array to 0
// Initializing dp array for base case of single digits
for (int i = 0; i < MAX_NUM; i++)
{
dp[1][i][i] = 1;
}
// Dynamic programming to calculate the number of ways to form numbers with given sum and number of digits
for (int N = 2; N <= MAX_NOS; N++)
{
for (int i = 1; i <= MAX_NUM; i++)
{
for (int j = 1; j <= MAX_SUM_VAL; j++)
{
if (j - i >= 0)
{
for (int k = 0; k < i; k++)
{
dp[N][i][j] += dp[N - 1][k][j - i];
}
}
}
}
}
cin >> n >> s; // Input for number of digits and required sum
SUM_VAL = 0; // Reset SUM_VAL to 0
// Calculating the total number of pairs satisfying the given conditions
for (int i = 0; i <= MAX_NUM; i++)
{
SUM_VAL += dp[n][i][s];
}
// Outputting the result
cout << "Number of digits " << n << " and Sum = " << s;
cout << "\nNumber of pairs: " << SUM_VAL << endl;
return 0; // Indicating successful completion of the program
}
Sample Output:
Sample Input: 2 5 Number of digits 2 and Sum = 5 Number of pairs: 3
Flowchart:
C++ Code Editor:
Previous: Write a C++ program which reads a sequence of integers and prints mode values of the sequence. The number of integers is greater than or equals to 1 and less than or equals to 100.
Next: Write a C++ program that accepts sales unit price and sales quantity of various items and compute total sales amount and the average sales quantity. All input values must greater than or equal to 0 and less than or equal to 1,000, and the number of pairs of sales unit and sales quantity does not exceed 100. If a fraction occurs in the average of the sales quantity, round the first decimal place.
What is the difficulty level of this exercise?
It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.
https://w3resource.com/cpp-exercises/basic/cpp-basic-exercise-72.php
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics