Ditulis dalam C++, cari bilangan pilih atur unik rentetan binari bermula dengan 1

Dalam masalah yang diberikan, kita diberi rentetan yang terdiri daripada 0 dan 1; kita perlu mencari jumlah nombor semua pilih atur bermula dengan 1. Oleh kerana jawapannya mungkin jumlah yang besar, kami mengambilnya modulo 1000000007 dan mengeluarkannya.

Input : str ="10101001001"
Output : 210

Input : str ="101110011"
Output : 56

Kami akan menyelesaikan masalah ini dengan menggunakan beberapa matematik gabungan dan menyediakan beberapa formula.

Kaedah Penyelesaian

Dalam kaedah ini kita akan mengira nombor 0 dan 1. Sekarang andaikan bahawa n ialah nombor 1 yang muncul dalam rentetan kami, m ialah bilangan 0 yang muncul dalam rentetan kami, dan L ialah panjang rentetan yang diberikan kami, jadi formula yang kami rumuskan untuk menyelesaikan masalah ini ialah (L- 1 )!/ (n-1) * m!.

Contoh

#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

Kerumitan masa atur cara yang diberi ialah O(N), dengan n ialah panjang rentetan yang diberikan.

Penjelasan kod di atas

Dalam kaedah ini kita mengira bilangan 1 dan 0 dalam rentetan, kini kita meletakkan 1 pada permulaan dan kini merumuskan semua kemungkinan 0 dalam rentetan panjang L-1 dan pilih atur 1. Dengan merumuskan pilih atur ini, kita mendapat formula (L-1) / (n-1)!

Kesimpulan

Dalam artikel ini kami menyelesaikan masalah mencari bilangan pilih atur unik rentetan binari bermula dengan 1 dengan menggunakan beberapa kombinatorik dan merumuskan formula.

Kami juga mempelajari program C++ dan kaedah lengkap (kaedah biasa) untuk menyelesaikan masalah ini. Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan lain-lain. Semoga artikel ini membantu anda.

Atas ialah kandungan terperinci Ditulis dalam C++, cari bilangan pilih atur unik rentetan binari bermula dengan 1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!