Count number of strings (made of R, G and B) using given combination
We need to make a string of size n. Each character of the string is either ‘R’, ‘B’ or ‘G’. In the final string there needs to be at least r number of ‘R’, at least b number of ‘B’ and at least g number of ‘G’ (such that r + g + b <= n). We need to find number of such strings possible.
Examples:
Input : n = 4, r = 1, b = 1, g = 1. Output: 36 No. of 'R' >= 1, No. of ‘G’ >= 1, No. of ‘B’ >= 1 and (No. of ‘R’) + (No. of ‘B’) + (No. of ‘G’) = n then following cases are possible: 1. RBGR and its 12 permutation 2. RBGB and its 12 permutation 3. RBGG and its 12 permutation Hence answer is 36.
Asked in : Directi
Implementation:
C++
// C++ program to count number of possible strings // with n characters. #include<bits/stdc++.h> using namespace std; // Function to calculate number of strings int possibleStrings( int n, int r, int b, int g) { // Store factorial of numbers up to n // for further computation int fact[n+1]; fact[0] = 1; for ( int i = 1; i <= n; i++) fact[i] = fact[i-1] * i; // Find the remaining values to be added int left = n - (r+g+b); int sum = 0; // Make all possible combinations // of R, B and G for the remaining value for ( int i = 0; i <= left; i++) { for ( int j = 0; j<= left-i; j++) { int k = left - (i+j); // Compute permutation of each combination // one by one and add them. sum = sum + fact[n] / (fact[i+r]*fact[j+b]*fact[k+g]); } } // Return total no. of strings/permutation return sum; } // Drivers code int main() { int n = 4, r = 2; int b = 0, g = 1; cout << possibleStrings(n, r, b, g); return 0; } |
Java
// Java program to count number of possible // strings with n characters. class GFG{ //Function to calculate number of strings static int possibleStrings( int n, int r, int b, int g) { // Store factorial of numbers up to n // for further computation int fact[] = new int [n+ 1 ]; fact[ 0 ] = 1 ; for ( int i = 1 ; i <= n; i++) fact[i] = fact[i- 1 ] * i; // Find the remaining values to be added int left = n - (r+g+b); int sum = 0 ; // Make all possible combinations // of R, B and G for the remaining value for ( int i = 0 ; i <= left; i++) { for ( int j = 0 ; j<= left-i; j++) { int k = left - (i+j); // Compute permutation of each combination // one by one and add them. sum = sum + fact[n] / (fact[i+r]*fact[j+b]*fact[k+g]); } } // Return total no. of strings/permutation return sum; } //Drivers code public static void main(String []args) { int n = 4 , r = 2 ; int b = 0 , g = 1 ; System.out.println(possibleStrings(n, r, b, g)); } } |
Python3
# Python 3 program to count number of # possible strings with n characters. # Function to calculate number of strings def possibleStrings(n, r, b, g): # Store factorial of numbers up to n # for further computation fact = [ 0 for i in range (n + 1 )] fact[ 0 ] = 1 for i in range ( 1 , n + 1 , 1 ): fact[i] = fact[i - 1 ] * i # Find the remaining values to be added left = n - (r + g + b) sum = 0 # Make all possible combinations of # R, B and G for the remaining value for i in range ( 0 , left + 1 , 1 ): for j in range ( 0 , left - i + 1 , 1 ): k = left - (i + j) # Compute permutation of each # combination one by one and add them. sum = ( sum + fact[n] / (fact[i + r] * fact[j + b] * fact[k + g])) # Return total no. of # strings/permutation return sum # Driver code if __name__ = = '__main__' : n = 4 r = 2 b = 0 g = 1 print ( int (possibleStrings(n, r, b, g))) # This code is contributed by # Sanjit_Prasad |
C#
// C# program to count number of possible // strings with n characters. using System; class GFG { //Function to calculate number of strings static int possibleStrings( int n, int r, int b, int g) { // Store factorial of numbers up to n // for further computation int [] fact = new int [n + 1]; fact[0] = 1; for ( int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i; // Find the remaining values to be added int left = n - (r + g + b); int sum = 0; // Make all possible combinations // of R, B and G for the remaining value for ( int i = 0; i <= left; i++) { for ( int j = 0; j <= left - i; j++) { int k = left - (i + j); // Compute permutation of each combination // one by one and add them. sum = sum + fact[n] / (fact[i + r] * fact[j + b] * fact[k + g]); } } // Return total no. of strings/permutation return sum; } //Drivers code public static void Main() { int n = 4, r = 2; int b = 0, g = 1; Console.WriteLine(possibleStrings(n, r, b, g)); } } // This Code is contributed by Code_Mech. |
PHP
<?php // PHP program to count number // of possible strings with // n characters. // Function to calculate // number of strings function possibleStrings( $n , $r , $b , $g ) { // Store factorial of // numbers up to n for // further computation $fact [0] = 1; for ( $i = 1; $i <= $n ; $i ++) $fact [ $i ] = $fact [ $i - 1] * $i ; // Find the remaining // values to be added $left = $n - ( $r + $g + $b ); $sum = 0; // Make all possible combinations // of R, B and G for the remaining value for ( $i = 0; $i <= $left ; $i ++) { for ( $j = 0; $j <= $left - $i ; $j ++) { $k = $left - ( $i + $j ); // Compute permutation of // each combination one // by one and add them. $sum = $sum + $fact [ $n ] / ( $fact [ $i + $r ] * $fact [ $j + $b ] * $fact [ $k + $g ]); } } // Return total no. of // strings/permutation return $sum ; } // Driver Code $n = 4; $r = 2; $b = 0; $g = 1; echo possibleStrings( $n , $r , $b , $g ); // This code is contributed by jit_t. ?> |
Javascript
<script> // Javascript program to count number of possible // strings with n characters. // Function to calculate number of strings function possibleStrings(n,r,b,g) { // Store factorial of numbers up to n // for further computation let fact = new Array(n+1); fact[0] = 1; for (let i = 1; i <= n; i++) fact[i] = fact[i-1] * i; // Find the remaining values to be added let left = n - (r+g+b); let sum = 0; // Make all possible combinations // of R, B and G for the remaining value for (let i = 0; i <= left; i++) { for (let j = 0; j<= left-i; j++) { let k = left - (i+j); // Compute permutation of each combination // one by one and add them. sum = sum + fact[n] / (fact[i+r]*fact[j+b]*fact[k+g]); } } // Return total no. of strings/permutation return sum; } // Drivers code let n = 4, r = 2; let b = 0, g = 1; document.write(possibleStrings(n, r, b, g)); // This code is contributed by avanitrachhadiya2155 </script> |
Output
22
Time Complexity: O(n*n).
Auxiliary Space: O(n).
To handle n with large numbers, we can use the concept of Large Factorial.