Different ways to represent N as sum of K non-zero integers
Last Updated :
23 May, 2022
Given N and K. The task is to find out how many different ways there are to represent N as the sum of K non-zero integers.
Examples:
Input: N = 5, K = 3
Output: 6
The possible combinations of integers are:
( 1, 1, 3 )
( 1, 3, 1 )
( 3, 1, 1 )
( 1, 2, 2 )
( 2, 2, 1 )
( 2, 1, 2 )
Input: N = 10, K = 4
Output: 84
The approach to the problem is to observe a sequence and use combinations to solve the problem. To obtain a number N, N 1's are required, summation of N 1's will give N. The problem allows you to use K integers only to make N.
Observation:
Let's take N = 5 and K = 3, then all
possible combinations of K numbers are: ( 1, 1, 3 )
( 1, 3, 1 )
( 3, 1, 1 )
( 1, 2, 2 )
( 2, 2, 1 )
( 2, 1, 2 )
The above can be rewritten as: ( 1, 1, 1 + 1 + 1 )
( 1, 1 + 1 + 1, 1 )
( 1 + 1 + 1, 1, 1 )
( 1, 1 + 1, 1 + 1 )
( 1 + 1, 1 + 1, 1 )
( 1 + 1, 1, 1 + 1 )
From above, a conclusion can be drawn that of N 1's, k-1 commas have to be placed in between N 1's and the remaining places are to be filled with '+' signs. All combinations of placing k-1 commas and placing '+' signs in the remaining places will be the answer. So, in general, for N there will be N-1 spaces between all 1, and out of those choose k-1 and place a comma in between those 1. In between the rest 1's, place '+' signs. So the way of choosing K-1 objects out of N-1 is N-1 \choose K-1 . The dynamic programming approach is used to calculate N-1 \choose K-1 .
Below is the implementation of the above approach:
C++
// CPP program to calculate Different ways to
// represent N as sum of K non-zero integers.
#include <bits/stdc++.h>
using namespace std;
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
int C[n + 1][k + 1];
int i, j;
// Calculate value of Binomial Coefficient in bottom up manner
for (i = 0; i <= n; i++) {
for (j = 0; j <= min(i, k); j++) {
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previously stored values
else
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
return C[n][k];
}
// Driver Code
int main()
{
int n = 5, k = 3;
cout << "Total number of different ways are "
<< binomialCoeff(n - 1, k - 1);
return 0;
}
// C program to calculate Different ways to
// represent N as sum of K non-zero integers.
#include <stdio.h>
int min(int a, int b)
{
int min = a;
if(min > b)
min = b;
return min;
}
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
int C[n + 1][k + 1];
int i, j;
// Calculate value of Binomial Coefficient in bottom up manner
for (i = 0; i <= n; i++) {
for (j = 0; j <= min(i, k); j++) {
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previously stored values
else
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
return C[n][k];
}
// Driver Code
int main()
{
int n = 5, k = 3;
printf("Total number of different ways are %d",binomialCoeff(n - 1, k - 1));
return 0;
}
// This code is contributed by kothavvsaakash.
// Java program to calculate
// Different ways to represent
// N as sum of K non-zero integers.
import java.io.*;
class GFG
{
// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeff(int n,
int k)
{
int C[][] = new int [n + 1][k + 1];
int i, j;
// Calculate value of Binomial
// Coefficient in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0;
j <= Math.min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using
// previously stored values
else
C[i][j] = C[i - 1][j - 1] +
C[i - 1][j];
}
}
return C[n][k];
}
// Driver Code
public static void main (String[] args)
{
int n = 5, k = 3;
System.out.println( "Total number of " +
"different ways are " +
binomialCoeff(n - 1,
k - 1));
}
}
// This code is contributed
// by anuj_67.
# python 3 program to calculate Different ways to
# represent N as sum of K non-zero integers.
# Returns value of Binomial Coefficient C(n, k)
def binomialCoeff(n, k):
C = [[0 for i in range(k+1)]for i in range(n+1)]
# Calculate value of Binomial Coefficient in bottom up manner
for i in range(0,n+1,1):
for j in range(0,min(i, k)+1,1):
# Base Cases
if (j == 0 or j == i):
C[i][j] = 1
# Calculate value using previously stored values
else:
C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
return C[n][k]
# Driver Code
if __name__ == '__main__':
n = 5
k = 3
print("Total number of different ways are",binomialCoeff(n - 1, k - 1))
# This code is contributed by
# Sanjit_Prasad
// C# program to calculate
// Different ways to represent
// N as sum of K non-zero integers.
using System;
class GFG
{
// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeff(int n,
int k)
{
int [,]C = new int [n + 1,
k + 1];
int i, j;
// Calculate value of
// Binomial Coefficient
// in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0;
j <= Math.Min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i, j] = 1;
// Calculate value using
// previously stored values
else
C[i, j] = C[i - 1, j - 1] +
C[i - 1, j];
}
}
return C[n,k];
}
// Driver Code
public static void Main ()
{
int n = 5, k = 3;
Console.WriteLine( "Total number of " +
"different ways are " +
binomialCoeff(n - 1,
k - 1));
}
}
// This code is contributed
// by anuj_67.
<?php
// PHP program to calculate
// Different ways to represent
// N as sum of K non-zero integers.
// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff($n, $k)
{
$C = array(array());
$i; $j;
// Calculate value of Binomial
// Coefficient in bottom up manner
for ($i = 0; $i <= $n; $i++)
{
for ($j = 0;
$j <= min($i, $k); $j++)
{
// Base Cases
if ($j == 0 or $j == $i)
$C[$i][$j] = 1;
// Calculate value using
// previously stored values
else
$C[$i][$j] = $C[$i - 1][$j - 1] +
$C[$i - 1][$j];
}
}
return $C[$n][$k];
}
// Driver Code
$n = 5; $k = 3;
echo "Total number of " ,
"different ways are " ,
binomialCoeff($n - 1,
$k - 1);
// This code is contributed
// by anuj_67.
?>
<script>
// Javascript program to calculate
// Different ways to represent
// N as sum of K non-zero integers.
// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff(n, k)
{
let C = new Array(n + 1);
for(let i = 0; i < n + 1; i ++)
{
C[i] = new Array(k + 1);
for(let j = 0; j < k + 1; j++)
{
C[i][j] = 0;
}
}
let i, j;
// Calculate value of Binomial
// Coefficient in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0; j <= Math.min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using
// previously stored values
else
C[i][j] = C[i - 1][j - 1] +
C[i - 1][j];
}
}
return C[n][k];
}
let n = 5, k = 3;
document.write( "Total number of " +
"different ways are " +
binomialCoeff(n - 1,
k - 1));
</script>
Output: Total number of different ways are 6
Time Complexity: O(N * K)
Auxiliary Space: O(N * K)
Similar Reads
Number of ways in which N can be represented as the sum of two positive integers
Given a number N, the task is to find the number of unique ways in which N can be represented as a sum of two positive integers.Examples: Input: N = 7 Output: 3 (1 + 6), (2 + 5) and (3 + 4).Input: N = 200 Output: 100 Approach: The number of ways in which the number can be expressed as the sum of two
3 min read
Ways to write n as sum of two or more positive integers
For a given number n > 0, find the number of different ways in which n can be written as a sum of two or more positive integers. Examples: Input : n = 5 Output : 6 Explanation : All possible six ways are : 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 Input : 4 Output : 4 Explan
6 min read
Ways to write N as sum of two or more positive integers | Set-2
Given a number N, the task is to find the number of ways N can be partitioned, i.e. the number of ways that N can be expressed as a sum of positive integers.Note: N should also be considered itself a way to express it as a sum of positive integers. Examples: Input: N = 5 Output: 7 5 can be partition
5 min read
Number of ways to represent a number as sum of k fibonacci numbers
Given two numbers N and K. Find the number of ways to represent N as the sum of K Fibonacci numbers. Examples: Input : n = 12, k = 1 Output : 0 Input : n = 13, k = 3 Output : 2 Explanation : 2 + 3 + 8, 3 + 5 + 5. Approach: The Fibonacci series is f(0)=1, f(1)=2 and f(i)=f(i-1)+f(i-2) for i>1. Let
8 min read
Represent K^N as the sum of exactly N numbers
Given two numbers N and K, the task is to represent KN as the sum of exactly N numbers. Print NA if no such numbers are possible.Examples: Input: N = 5, K = 2 Output: 2 2 4 8 16 Explanation: 2 + 2 + 4 + 8 + 16 = 32 = 25Input: N = 4, K = 3 Output: 3 6 18 54 Explanation: 3 + 6 + 18 + 54 = 81 = 34 Appr
4 min read
Number of ways to write N as a sum of K non-negative integers
Given two positive integers N and K, the task is to count the number of ways to write N as a sum of K non-negative integers. Examples: Input: N = 2, K = 3 Output: 6 Explanation: The total ways in which 2 can be split into K non-negative integers are: 1. (0, 0, 2) 2. (0, 2, 0) 3. (2, 0, 0) 4. (0, 1,
15+ min read
Represent N as sum of K even numbers
Given two integers N and K, the task is to represent N as the sum of K even number. If it is not possible to represent the number, print -1.Note: The representation may contain duplicate even numbers. Examples: Input: N = 6, K = 3 Output: 2 2 2 Explanation: The given number 6 can be represented as 2
4 min read
Sum of two numbers where one number is represented as array of digits
Given an array arr[] of digits and an integer K, the task is to find num(arr) + K where num(arr) is the number formed by concatenating all the digits of the array. Examples: Input: arr[] = {2, 7, 4}, K = 181 Output: 455 274 + 181 = 455 Input: arr[] = {6}, K = 815 Output: 821 6 + 815 = 821 Approach:
10 min read
Check whether a number can be represented as sum of K distinct positive integers
Given two integers N and K, the task is to check whether N can be represented as sum of K distinct positive integers. Examples: Input: N = 12, K = 4 Output: Yes N = 1 + 2 + 4 + 5 = 12 (12 as sum of 4 distinct integers) Input: N = 8, K = 4 Output: No Recommended: Please try your approach on {IDE} fir
10 min read
Print all possible ways to write N as sum of two or more positive integers
Given an integer N, the task is to print all the possible ways in which N can be written as the sum of two or more positive integers.Examples: Input: N = 4 Output: 1 1 1 1 1 1 2 1 3 2 2 Input: N = 3 Output: 1 1 1 1 2 Approach: The idea is to use recursion to solve this problem. The idea is to consid
7 min read