Écrit en C++, trouvez le nombre de permutations uniques d'une chaîne binaire commençant par 1

Dans le problème donné, on nous donne une chaîne composée de 0 et 1 ; nous devons trouver le nombre total de toutes les permutations commençant par 1. Puisque la réponse peut être un nombre énorme, nous la prenons modulo 1000000007 et la produisons.

Input : str ="10101001001"
Output : 210

Input : str ="101110011"
Output : 56

Nous allons résoudre ce problème en appliquant des mathématiques combinatoires et en mettant en place des formules.

Méthode de solution

Dans cette méthode, nous compterons le nombre de 0 et 1. Supposons maintenant que n soit le nombre de 1 qui apparaissent dans notre chaîne, m est le nombre de 0 qui apparaissent dans notre chaîne et L est la longueur de notre chaîne donnée, donc la formule que nous formulons pour résoudre ce problème est (L- 1 )!/ (n-1)!

Exemple

#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;
}

Sortie

56

La complexité temporelle du programme donné est O(N), où n est la longueur de la chaîne donnée.

Explication du code ci-dessus

Dans cette méthode, nous comptons le nombre de 1 et de 0 dans la chaîne, maintenant nous mettons un 1 au début et formulons maintenant tous les 0 possibles dans la chaîne de longueur L-1 et 1 permutation. En formulant cette permutation, nous obtenons la formule de (L-1)! / (n-1)! * m!, où (n-1)! est la permutation du 1 restant et m!

Conclusion

Dans cet article, nous avons résolu le problème de trouver le nombre de permutations uniques d'une chaîne binaire commençant par 1 en appliquant des combinatoires et en formulant une formule.

Nous avons également appris le programme C++ et la méthode complète (méthode normale) pour résoudre ce problème. Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et autres. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!