Given three integers N, P, and K, the task is to find the total number of ways to divide N into K integers having sum N where each integer is ? P.
Examples:
Input: K = 3, N = 8, P = 2
Output: 6
Explanation:
Six possible solutions are: {2, 2, 4}, {2, 3, 3}, {2, 4, 2}, {3, 2, 3}, {3, 3, 2}, {4, 2, 2}
Each of the above integers in all combinations are ? P(= 2) and sum of all the combinations is N(=8).Input: K = 2, N = 7, P = 2
Output: 4
Explanation:
Four possible solutions are: {4, 3}, {3, 4}, {5, 2}, {2, 5}
Each of the above integers in all combinations are ? P(= 2) and sum of all the combinations is N(= 7).
Naive Approach: The simplest approach is to try all possible combinations of K integers having sum N and check if they satisfy the above conditions or not. There are K positions and in each position, N integers can be placed. Therefore, the total number of combinations to check is NK.
Time Complexity: O(NK)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use the approach discussed in this article and the given above conditions can be written in terms of a linear equation is:
To find the number of solutions for the equation X1 + X2 + X3 + … + XK = N where Xi ? P.
Assume Xi‘ = Xi – P.
Therefore, the equation reduces to:
X1‘ + X2‘ + X3‘ + … + XK‘ = N – K*P
As per the above equations, the given problem reduces to finding total number of ways to split N – K * P into K integers. Print the total number of ways found above as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that finds the value of// the Binomial Coefficient C(n, k)int binomialCoeff(int n, int k){ int C[n + 1][k + 1]; int i, j; // Stores the value of Binomial // Coefficient in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= min(i, k); j++) { // Base Case if (j == 0 || j == i) C[i][j] = 1; // Find the value using // previously stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } // Return the value of C(N, K) return C[n][k];}// Function that count the number of// ways to divide N into K integers// >= P such that their sum is Nint waysToSplitN(int k, int n, int P){ // Update the value of N int new_N = n - k * P; // Find the binomial coefficient // recursively return binomialCoeff(new_N + k - 1, new_N);}// Driver Codeint main(){ // Given K, N, and P int K = 3, N = 8, P = 2; cout << waysToSplitN(K, N, P); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG{// Function that finds the value of// the Binomial Coefficient C(n, k)static int binomialCoeff(int n, int k){ int [][]C = new int[n + 1][k + 1]; int i, j; // Stores the value of Binomial // Coefficient in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= Math.min(i, k); j++) { // Base Case if (j == 0 || j == i) C[i][j] = 1; // Find the value using // previously stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } // Return the value of C(N, K) return C[n][k];}// Function that count the number of// ways to divide N into K integers// >= P such that their sum is Nstatic int waysToSplitN(int k, int n, int P){ // Update the value of N int new_N = n - k * P; // Find the binomial coefficient // recursively return binomialCoeff(new_N + k - 1, new_N);}// Driver Codepublic static void main(String[] args){ // Given K, N, and P int K = 3, N = 8, P = 2; System.out.print(waysToSplitN(K, N, P));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach # Function that finds the value of# the Binomial Coefficient C(n, k)def binomialCoeff(n, k): C = [[0 for x in range(k + 1)] for y in range(n + 1)] # Stores the value of Binomial # Coefficient in bottom up manner for i in range(n + 1): for j in range(min(i, k) + 1): # Base Case if(j == 0 or j == i): C[i][j] = 1 # Find the value using # previously stored values else: C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) # Return the value of C(N, K) return C[n][k]# Function that count the number of# ways to divide N into K integers# >= P such that their sum is Ndef waysToSplitN(k, n, P): # Update the value of N new_N = n - k * P # Find the binomial coefficient # recursively return binomialCoeff(new_N + k - 1, new_N)# Driver Code# Given K, N, and P K = 3N = 8P = 2print(waysToSplitN(K, N, P))# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;class GFG{ // Function that finds the value of// the Binomial Coefficient C(n, k)static int binomialCoeff(int n, int k){ int [,] C = new int[n + 1, k + 1]; int i, j; // Stores the value of Binomial // Coefficient in bottom up manner for(i = 0; i <= n; i++) { for(j = 0; j <= Math.Min(i, k); j++) { // Base Case if (j == 0 || j == i) C[i, j] = 1; // Find the value using // previously stored values else C[i, j] = C[i - 1, j - 1] + C[i - 1, j]; } } // Return the value of C(N, K) return C[n, k];} // Function that count the number of// ways to divide N into K integers// >= P such that their sum is Nstatic int waysToSplitN(int k, int n, int P){ // Update the value of N int new_N = n - k * P; // Find the binomial coefficient // recursively return binomialCoeff(new_N + k - 1, new_N);} // Driver Codepublic static void Main(){ // Given K, N, and P int K = 3, N = 8, P = 2; Console.Write(waysToSplitN(K, N, P));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program to implement// the above approach// Function that finds the value of// the Binomial Coefficient C(n, k)function binomialCoeff(n, k){ let C = new Array(n + 1); // Loop to create 2D array using 1D array for (let i = 0; i < C.length; i++) { C[i] = new Array(2); } let i, j; // Stores the value of Binomial // Coefficient in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= Math.min(i, k); j++) { // Base Case if (j == 0 || j == i) C[i][j] = 1; // Find the value using // previously stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } // Return the value of C(N, K) return C[n][k];} // Function that count the number of// ways to divide N into K integers// >= P such that their sum is Nfunction waysToSplitN(k, n, P){ // Update the value of N let new_N = n - k * P; // Find the binomial coefficient // recursively return binomialCoeff(new_N + k - 1, new_N);}// Driver Code // Given K, N, and P let K = 3, N = 8, P = 2; document.write(waysToSplitN(K, N, P)); </script> |
Output:
6
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient approach : Space optimization
In previous approach the dp[i][j] is depend upon the current and previous row of 2D matrix. So to optimize space we use two vectors curr and prev that keep track of current and previous row of DP.
Implementation Steps:
- Initialize two vectors curr and prev to keep track of only current and previous row of Dp with 0.
- Now iterative over subproblems and get the current computation.
- While iteration initialize curr vector.
- Now compute the current value by the help of prev vector and store that value in curr.
- After every iteration store values of curr vector in prev vector for further iteration.
- At last return the answer stored in curr[k] .
Implementation:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that finds the value of// the Binomial Coefficient C(n, k)int binomialCoeff(int n, int k){ // initialize two vectors curr and prev // to keep track of current and previous row od DP vector<int> prev(k + 1, 0); vector<int> curr(k + 1, 0); // Stores the value of Binomial // Coefficient in bottom up manner for (int i = 0; i <= n; i++) { for (int j = 0; j <= min(i, k); j++) { // Base Case if (j == 0 || j == i) curr[j] = 1; // Find the value using // previously stored values else curr[j] = prev[j - 1] + prev[j]; } // assigning values of prev to curr // further iterations prev = curr; } // Return answer return curr[k];}// Function that count the number of// ways to divide N into K integers// >= P such that their sum is Nint waysToSplitN(int k, int n, int P){ // Update the value of N int new_N = n - k * P; // Find the binomial coefficient // recursively return binomialCoeff(new_N + k - 1, new_N);}// Driver Codeint main(){ // Given K, N, and P int K = 3, N = 8, P = 2; cout << waysToSplitN(K, N, P); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;public class Main { // Function that finds the value of // the Binomial Coefficient C(n, k) static int binomialCoeff(int n, int k) { // initialize two arrays curr and prev // to keep track of current and previous row of DP int[] prev = new int[k + 1]; int[] curr = new int[k + 1]; // Stores the value of Binomial // Coefficient in bottom up manner for (int i = 0; i <= n; i++) { for (int j = 0; j <= Math.min(i, k); j++) { // Base Case if (j == 0 || j == i) curr[j] = 1; // Find the value using // previously stored values else curr[j] = prev[j - 1] + prev[j]; } // assigning values of prev to curr // further iterations prev = curr.clone(); } // Return answer return curr[k]; } // Function that count the number of // ways to divide N into K integers // >= P such that their sum is N static int waysToSplitN(int k, int n, int P) { // Update the value of N int new_N = n - k * P; // Find the binomial coefficient // recursively return binomialCoeff(new_N + k - 1, new_N); } // Driver Code public static void main(String[] args) { // Given K, N, and P int K = 3, N = 8, P = 2; System.out.println(waysToSplitN(K, N, P)); }} |
Python3
def binomial_coeff(n, k): # initialize two lists curr and prev # to keep track of current and previous row od DP prev = [0] * (k + 1) curr = [0] * (k + 1) # Stores the value of Binomial # Coefficient in bottom up manner for i in range(n + 1): for j in range(min(i, k), -1, -1): # Base Case if j == 0 or j == i: curr[j] = 1 # Find the value using # previously stored values else: curr[j] = prev[j - 1] + prev[j] # assigning values of prev to curr # further iterations prev = curr.copy() # Return answer return curr[k]# Function that count the number of# ways to divide N into K integers# >= P such that their sum is Ndef ways_to_split_n(k, n, p): # Update the value of N new_n = n - k * p # Find the binomial coefficient recursively return binomial_coeff(new_n + k - 1, new_n)# Driver Codeif __name__ == '__main__': # Given K, N, and P k = 3 n = 8 p = 2 print(ways_to_split_n(k, n, p)) |
C#
using System;using System.Collections.Generic;public class GFG { // Function that finds the value of // the Binomial Coefficient C(n, k) public static int binomialCoeff(int n, int k) { // initialize two lists curr and prev // to keep track of current and previous row of DP List<int> prev = new List<int>(); List<int> curr = new List<int>(); // Initialize prev with all 0s for (int i = 0; i <= k; i++) prev.Add(0); // Initialize curr with all 0s for (int i = 0; i <= k; i++) curr.Add(0); // Stores the value of Binomial // Coefficient in bottom up manner for (int i = 0; i <= n; i++) { for (int j = 0; j <= Math.Min(i, k); j++) { // Base Case if (j == 0 || j == i) curr[j] = 1; // Find the value using // previously stored values else curr[j] = prev[j - 1] + prev[j]; } // assigning values of prev to curr // further iterations prev = new List<int>(curr); } // Return answer return curr[k]; } // Function that count the number of // ways to divide N into K integers // >= P such that their sum is N public static int waysToSplitN(int k, int n, int P) { // Update the value of N int new_N = n - k * P; // Find the binomial coefficient // recursively return binomialCoeff(new_N + k - 1, new_N); } // Driver Code public static void Main() { // Given K, N, and P int K = 3, N = 8, P = 2; Console.WriteLine(waysToSplitN(K, N, P)); }} |
Javascript
// Function that finds the value of// the Binomial Coefficient C(n, k)function binomialCoeff(n, k){ // initialize two arrays curr and prev // to keep track of current and previous row od DP let prev = new Array(k + 1).fill(0); let curr = new Array(k + 1).fill(0); // Stores the value of Binomial // Coefficient in bottom up manner for (let i = 0; i <= n; i++) { for (let j = 0; j <= Math.min(i, k); j++) { // Base Case if (j == 0 || j == i) { curr[j] = 1; } // Find the value using // previously stored values else { curr[j] = prev[j - 1] + prev[j]; } } // assigning values of prev to curr // further iterations prev = curr.slice(); } // Return answer return curr[k];}// Function that count the number of// ways to divide N into K integers// >= P such that their sum is Nfunction waysToSplitN(k, n, P) { // Update the value of N const newN = n - k * P; // Find the binomial coefficient // recursively return binomialCoeff(newN + k - 1, newN);}// Driver Codeconst K = 3;const N = 8;const P = 2;console.log(waysToSplitN(K, N, P)); |
Output:
6
Time Complexity: O(N*N)
Auxiliary Space: O(K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
