Given a binary string composed of 0’s and 1’s. The task is to find the number of unique permutation of the string which starts with 1.
Note: Since the answer can be very large, print the answer under modulo 109 + 7.
Examples:
Input : str ="10101001001" Output : 210 Input : str ="101110011" Output : 56
The idea is to first find the count of 1’s and the count of 0’s in the given string. Now let us consider that the string is of length 
and the string consists of at least one 1. Let the number of 1’s be 
and the number of 0’s be 
. Out of n number of 1’s we have to place one 1 at the beginning of the string so we have n-1 1’s left and m 0’s we have to permute these (n-1) 1’s and m 0’s in length (L-1) of the string.
Therefore, the number of permutation will be:
(L-1)! / ((n-1)!*(m)!)
Below is the implementation of the above idea:
C++
// C++ program to find number of unique permutations// of a binary string starting with 1#include <bits/stdc++.h>using namespace std;#define MAX 1000003#define mod 1000000007// Array to store factorial of i at// i-th indexlong long fact[MAX];// Precompute factorials under modulo mod// upto MAXvoid factorial(){ // factorial of 0 is 1 fact[0] = 1; for (int i = 1; i < MAX; i++) { fact[i] = (fact[i - 1] * i) % mod; }}// Iterative Function to calculate (x^y)%p in O(log y)long long power(long long x, long long y, long long p){ long long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// Function to find the modular inverselong long inverse(int n){ return power(n, mod - 2, mod);}// Function to find the number of permutation// starting with 1 of a binary stringint countPermutation(string s){ // Generate factorials upto MAX factorial(); int length = s.length(), num1 = 0, num0; long long count = 0; // find number of 1's for (int i = 0; i < length; i++) { if (s[i] == '1') num1++; } // number of 0's num0 = length - num1; // Find the number of permutation of // string starting with 1 using the formulae: // (L-1)! / ((n-1)!*(m)!) count = (fact[length - 1] * inverse((fact[num1 - 1] * fact[num0]) % mod)) % mod; return count;}// Driver codeint main(){ string str = "10101001001"; cout << countPermutation(str); return 0;} |
Java
// Java program to find number of unique permutations // of a binary string starting with 1 public class Improve { final static int MAX = 1000003 ; final static int mod = 1000000007 ; // Array to store factorial of i at // i-th index static long fact[] = new long [MAX]; // Pre-compute factorials under modulo mod // upto MAX static void factorial() { // factorial of 0 is 1 fact[0] = 1; for (int i = 1; i < MAX; i++) { fact[i] = (fact[i - 1] * i) % mod; } } // Iterative Function to calculate (x^y)%p in O(log y) static long power(long x, long y, long p) { long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y % 2 != 0) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Function to find the modular inverse static long inverse(int n) { return power(n, mod - 2, mod); } // Function to find the number of permutation // starting with 1 of a binary string static int countPermutation(String s) { // Generate factorials upto MAX factorial(); int length = s.length(), num1 = 0, num0; long count = 0; // find number of 1's for (int i = 0; i < length; i++) { if (s.charAt(i) == '1') num1++; } // number of 0's num0 = length - num1; // Find the number of permutation of // string starting with 1 using the formulae: // (L-1)! / ((n-1)!*(m)!) count = (fact[length - 1] * inverse((int) ((fact[num1 - 1] * fact[num0]) % mod))) % mod; return (int) count; } // Driver code public static void main(String args[]) { String str = "10101001001"; System.out.println(countPermutation(str)); } // This Code is contributed by ANKITRAI1} |
Python 3
# Python 3 program to find number # of unique permutations of a# binary string starting with 1MAX = 1000003mod = 1000000007# Array to store factorial of # i at i-th indexfact = [0] * MAX# Precompute factorials under # modulo mod upto MAXdef factorial(): # factorial of 0 is 1 fact[0] = 1 for i in range(1, MAX): fact[i] = (fact[i - 1] * i) % mod# Iterative Function to calculate# (x^y)%p in O(log y)def power(x, y, p): res = 1 # Initialize result x = x % p # Update x if it is # more than or equal to p while (y > 0) : # If y is odd, multiply # x with result if (y & 1): res = (res * x) % p # y must be even now y = y >> 1 # y = y/2 x = (x * x) % p return res# Function to find the modular inversedef inverse( n): return power(n, mod - 2, mod)# Function to find the number of # permutation starting with 1 of # a binary stringdef countPermutation(s): # Generate factorials upto MAX factorial() length = len(s) num1 = 0 count = 0 # find number of 1's for i in range(length) : if (s[i] == '1'): num1 += 1 # number of 0's num0 = length - num1 # Find the number of permutation # of string starting with 1 using # the formulae: (L-1)! / ((n-1)!*(m)!) count = (fact[length - 1] * inverse((fact[num1 - 1] * fact[num0]) % mod)) % mod return count# Driver codeif __name__ =="__main__": s = "10101001001" print(countPermutation(s))# This code is contributed # by ChitraNayal |
C#
// C# program to find number of // unique permutations of a// binary string starting with 1 using System; class GFG{ static int MAX = 1000003 ; static int mod = 1000000007 ; // Array to store factorial // of i at i-th index static long []fact = new long [MAX]; // Pre-compute factorials under // modulo mod upto MAX static void factorial() { // factorial of 0 is 1 fact[0] = 1; for (int i = 1; i < MAX; i++) { fact[i] = (fact[i - 1] * i) % mod; } } // Iterative Function to calculate // (x^y)%p in O(log y) static long power(long x, long y, long p) { long res = 1; // Initialize result x = x % p; // Update x if it is more // than or equal to p while (y > 0) { // If y is odd, multiply // x with result if (y % 2 != 0) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Function to find the modular inverse static long inverse(int n) { return power(n, mod - 2, mod); } // Function to find the number of // permutation starting with 1 of// a binary string static int countPermutation(string s) { // Generate factorials upto MAX factorial(); int length = s.Length, num1 = 0, num0; long count = 0; // find number of 1's for (int i = 0; i < length; i++) { if (s[i] == '1') num1++; } // number of 0's num0 = length - num1; // Find the number of permutation // of string starting with 1 using // the formulae: (L-1)! / ((n-1)!*(m)!) count = (fact[length - 1] * inverse((int) ((fact[num1 - 1] * fact[num0]) % mod))) % mod; return (int) count; } // Driver code public static void Main() { string str = "10101001001"; Console.WriteLine(countPermutation(str)); } } // This code is contributed// by anuj_67 |
Javascript
<script>// Javascript program to find number of unique permutations// of a binary string starting with 1var MAX = 1000003var mod = 100000007// Array to store factorial of i at// i-th indexvar fact = Array(MAX);// Precompute factorials under modulo mod// upto MAXfunction factorial(){ // factorial of 0 is 1 fact[0] = 1; for (var i = 1; i < MAX; i++) { fact[i] = (fact[i - 1] * i) % mod; }}// Iterative Function to calculate (x^y)%p in O(log y)function power(x, y, p){ var res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// Function to find the modular inversefunction inverse(n){ return power(n, mod - 2, mod);}// Function to find the number of permutation// starting with 1 of a binary stringfunction countPermutation(s){ // Generate factorials upto MAX factorial(); var length = s.length, num1 = 0, num0; var count = 0; // find number of 1's for (var i = 0; i < length; i++) { if (s[i] == '1') num1++; } // number of 0's num0 = length - num1; // Find the number of permutation of // string starting with 1 using the formulae: // (L-1)! / ((n-1)!*(m)!) count = (fact[length - 1] * inverse((fact[num1 - 1] * fact[num0]) % mod)) % mod; return count;}// Driver codevar str = "10101001001";document.write( countPermutation(str));</script> |
Output:
210
Time Complexity: O(n), where n is the length of the string.
Auxilitary Space Complexity : O(n)
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!
