Written in C++, find the number of unique permutations of a binary string starting with 1

In the given problem, we are given a string consisting of 0 and 1; we need to find the total number of all permutations starting with 1. Since the answer may be a huge number, we take it modulo 1000000007 and output it.

Input : str ="10101001001" Output : 210 Input : str ="101110011" Output : 56

We will solve this problem by applying some combinatorial mathematics and establishing some formulas.

Solution method

In this method, we will count the number of 0 and 1. Now assume that n is the number of 1's that appear in our string, m is the number of 0's that appear in our string, and L is the length of our given string, so the formula we formulate to solve this problem is (L-1 )!/ (n-1)! * m!.

Example

#include  #define MOD 1000000007 // defining 1e9 + 7 as MOD using namespace std; long long fact(long long n) { if(n <= 1) return 1; return ((n % MOD) * (fact(n-1) % MOD)) % MOD; } int main() { string s = "101110011"; long long L = s.size(); // length of given string long long count_1 = 0, count_0 = 0; // keeping count of 1's and 0's for(auto x : s) { if(x == '1') count_1++; // frequency of 1's else count_0++; // frequency of 0's } if(count_1 == 0){ cout << "0\n"; // if string only consists of 0's so our answer will be 0 } else { long long factL = fact(L-1); // (L-1)! long long factn = fact(count_1 - 1); // (n-1)! long long factm = fact(count_0); // m! long long ans = factL / (factn * factm); // putting the formula cout << ans << "\n"; } return 0; }

Output

56

The time complexity of the given program is O(N), where n is the length of the given string.

Explanation of the above code

In this method we count the number of 1 and 0 in the string, now we put a 1 at the beginning and now in the length of L-1 Formulate all possible permutations of 0 and 1 in the string. By formulating this permutation, we get the formula of (L-1)! / (n-1)! * m!, where (n-1)! is the remaining 1 Permutation, m! is the permutation of 0.

Conclusion

In this article, we solved the problem of finding the number of unique permutations of a binary string starting with 1 by applying some combinatorics and formulating a formula.

We also learned the C program and complete method (normal method) to solve this problem. We can write the same program in other languages like C, Java, Python and others. Hope you find this article helpful.

The above is the detailed content of Written in C++, find the number of unique permutations of a binary string starting with 1. For more information, please follow other related articles on the PHP Chinese website!