Find Unique Permutations Starting with 1 of a Binary String Using C++

In the given problem, we are given a string consisting of 0’s and 1’s; we are required to find the total number of permutations such that the string starts with 1’s. As the answer can be a vast number, so we print as a mod with 1000000007.

Input : str ="10101001001"
Output : 210

Input : str ="101110011"
Output : 56

We will solve the given problem by applying some combinatorics and building up some formulas to solve this problem.

Approach to find The Solution

In the approach, we will calculate the number of 0's and 1's. Now let's suppose n is the number of 1's present in our string and m be the number of 0's present in our string and let L be the length of our given string, so the formula that we make 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'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 given program has a time complexity of O(N), where n is the length of our given string.

Explanation of the above code

In this approach, we are counting the number of 1’s and 0’s present inside of our string now, we place one at the starting and now formulate all the possible permutations of 0’s and 1’s in the string of length L-1 so by formulating this we get the formula of (L-1)! / (n-1)! * m! Where (n-1)! Are the permutations of the remaining 1’s, and m! is the permutation of the 0’s.

Conclusion

In this article, we solve a problem to find the number of unique permutations starting with 1 of a Binary String by applying some combinatorics and making up a formula for it.

We also learned the C++ program for this problem and the complete approach ( Normal) by which we solved this problem. We can write the same program in other languages such as C, java, python, and other languages. We hope you find this article helpful.