Number of ways to cut a stick of length N into K pieces
Given a stick of size N, find the number of ways in which it can be cut into K pieces such that length of every piece is greater than 0.
Examples :
Input : N = 5 K = 2 Output : 4
Input : N = 15 K = 5 Output : 1001
Solving this question is equivalent to solving the mathematics equation x1 + x2 + ….. + xK = N
We can solve this by using the bars and stars method in Combinatorics, from which we obtain the fact that the number of positive integral solutions to this equation is (N – 1)C(K – 1), where NCK is N! / ((N – K) ! * (K!)), where ! stands for factorial.
In C++ and Java, for large values of factorials, there might be overflow errors. In that case we can introduce a large prime number such as 107 + 7 to mod the answer. We can calculate nCr % p by using Lucas Theorem.
However, python can handle large values without overflow.
C++
// C++ program to calculate the number of ways // to divide a stick of length n into k pieces #include <bits/stdc++.h> using namespace std; // function to generate nCk or nChoosek unsigned long long nCr(unsigned long long n, unsigned long long r) { if (n < r) return 0; // Reduces to the form n! / n! if (r == 0) return 1; // nCr has been simplified to this form by // expanding numerator and denominator to // the form n(n - 1)(n - 2)...(n - r + 1) // ----------------------------- // (r!) // in the above equation, (n - r)! is cancelled // out in the numerator and denominator unsigned long long numerator = 1; for ( int i = n; i > n - r; i--) numerator = (numerator * i); unsigned long long denominator = 1; for ( int i = 1; i < r + 1; i++) denominator = (denominator * i); return (numerator / denominator); } // Returns number of ways to cut // a rod of length N into K pieces. unsigned long long countWays(unsigned long long N, unsigned long long K) { return nCr(N - 1, K - 1); } // Driver code int main() { unsigned long long N = 5; unsigned long long K = 2; cout << countWays(N, K); return 0; } |
Java
// Java program to find the number of ways in which // a stick of length n can be divided into K pieces import java.io.*; import java.util.*; class GFG { // function to generate nCk or nChoosek public static int nCr( int n, int r) { if (n < r) return 0 ; // Reduces to the form n! / n! if (r == 0 ) return 1 ; // nCr has been simplified to this form by // expanding numerator and denominator to // the form n(n - 1)(n - 2)...(n - r + 1) // ----------------------------- // (r!) // in the above equation, (n-r)! is cancelled // out in the numerator and denominator int numerator = 1 ; for ( int i = n ; i > n - r ; i--) numerator = (numerator * i); int denominator = 1 ; for ( int i = 1 ; i < r + 1 ; i++) denominator = (denominator * i); return (numerator / denominator); } // Returns number of ways to cut // a rod of length N into K pieces public static int countWays( int N, int K) { return nCr(N - 1 , K - 1 ); } public static void main(String[] args) { int N = 5 ; int K = 2 ; System.out.println(countWays(N, K)); } } |
Python3
# Python program to find the number # of ways in which a stick of length # n can be divided into K pieces # function to generate nCk or nChoosek def nCr(n, r): if (n < r): return 0 # reduces to the form n! / n! if (r = = 0 ): return 1 # nCr has been simplified to this form by # expanding numerator and denominator to # the form n(n - 1)(n - 2)...(n - r + 1) # ----------------------------- # (r!) # in the above equation, (n-r)! is cancelled # out in the numerator and denominator numerator = 1 for i in range (n, n - r, - 1 ): numerator = numerator * i denominator = 1 for i in range ( 1 , r + 1 ): denominator = denominator * i return (numerator / / denominator) # Returns number of ways to cut # a rod of length N into K pieces. def countWays(N, K) : return nCr(N - 1 , K - 1 ); # Driver code N = 5 K = 2 print (countWays(N, K)) |
C#
// C# program to find the number of // ways in which a stick of length n // can be divided into K pieces using System; class GFG { // function to generate nCk or nChoosek public static int nCr( int n, int r) { if (n < r) return 0; // Reduces to the form n! / n! if (r == 0) return 1; // nCr has been simplified to this form by // expanding numerator and denominator to // the form n(n - 1)(n - 2)...(n - r + 1) // ----------------------------- // (r!) // in the above equation, (n-r)! is cancelled // out in the numerator and denominator int numerator = 1; for ( int i = n; i > n - r; i--) numerator = (numerator * i); int denominator = 1; for ( int i = 1; i < r + 1; i++) denominator = (denominator * i); return (numerator / denominator); } // Returns number of ways to cut // a rod of length N into K pieces public static int countWays( int N, int K) { return nCr(N - 1, K - 1); } public static void Main() { int N = 5; int K = 2; Console.Write(countWays(N, K)); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to calculate the // number of ways to divide a // stick of length n into k pieces // function to generate nCk or nChoosek function nCr( $n , $r ) { if ( $n < $r ) return 0; // Reduces to the form n! / n! if ( $r == 0) return 1; // nCr has been simplified to this form by // expanding numerator and denominator to // the form n(n - 1)(n - 2)...(n - r + 1) // ----------------------------- // (r!) // in the above equation, (n - r)! is cancelled // out in the numerator and denominator $numerator = 1; for ( $i = $n ; $i > $n - $r ; $i --) $numerator = ( $numerator * $i ); $denominator = 1; for ( $i = 1; $i < $r + 1; $i ++) $denominator = ( $denominator * $i ); return ( floor ( $numerator / $denominator )); } // Returns number of ways to cut // a rod of length N into K pieces. function countWays( $N , $K ) { return nCr( $N - 1, $K - 1); } // Driver code $N = 5; $K = 2; echo countWays( $N , $K ); return 0; // This code is contributed by nitin mittal. ?> |
Javascript
<script> //Javascript Implementation // to calculate the number of ways // to divide a stick of length n into k pieces // function to generate nCk or nChoosek function nCr(n,r) { if (n < r) return 0; // Reduces to the form n! / n! if (r == 0) return 1; // nCr has been simplified to this form by // expanding numerator and denominator to // the form n(n - 1)(n - 2)...(n - r + 1) // ----------------------------- // (r!) // in the above equation, (n - r)! is cancelled // out in the numerator and denominator var numerator = 1; for ( var i = n; i > n - r; i--) numerator = (numerator * i); var denominator = 1; for ( var i = 1; i < r + 1; i++) denominator = (denominator * i); return Math.floor(numerator / denominator); } // Returns number of ways to cut // a rod of length N into K pieces. function countWays(N,K) { return nCr(N - 1, K - 1); } // Driver code var N = 5; var K = 2; document.write(countWays(N, K)); // This code is contributed by shubhamsingh10 </script> |
4
Time complexity: O(N)
Auxiliary space: O(1)
Exercise :
Extend the above problem with 0 length pieces allowed. Hint : The number of solutions can similarly be found by writing each xi as yi – 1, and we get an equation y1 + y2 + ….. + yK = N + K. The number of solutions to this equation is (N + K – 1)C(K – 1)