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 <bits/stdc++.h>
#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&#39;s and 0&#39;s
   for(auto x : s) {
      if(x == &#39;1&#39;)
         count_1++; // frequency of 1&#39;s
      else
        count_0++; // frequency of 0&#39;s
   }
   if(count_1 == 0){
      cout << "0\n"; // if string only consists of 0&#39;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!