Trong bài toán đã cho, chúng ta được cung cấp một chuỗi bao gồm 0 và 1; chúng tôi được yêu cầu phải tìm tổng số hoán vị sao cho chuỗi bắt đầu bằng 1’s. Vì câu trả lời có thể là một số lớn, vì vậy chúng tôi in dưới dạng mod với 1000000007.
Input : str ="10101001001" Output : 210 Input : str ="101110011" Output : 56
Chúng tôi sẽ giải quyết vấn đề đã cho bằng cách áp dụng một số tổ hợp và xây dựng một số công thức để giải quyết vấn đề này.
Phương pháp tiếp cận để tìm ra giải pháp
Trong cách tiếp cận, chúng tôi sẽ tính toán số của 0 và 1. Bây giờ, giả sử n là số 1 có trong chuỗi của chúng ta và m là số 0 có trong chuỗi của chúng ta và gọi L là độ dài của chuỗi đã cho của chúng ta, vì vậy công thức mà chúng ta đưa ra để giải quyết vấn đề này là (L-1 )! / (n-1)! * m !.
Ví dụ
#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;
} Đầu ra
56
Chương trình đã cho có độ phức tạp về thời gian là O (N), trong đó n là độ dài của chuỗi đã cho của chúng ta.
Giải thích về đoạn mã trên
Trong cách tiếp cận này, chúng tôi đang đếm số lượng của 1 và 0 hiện có bên trong chuỗi của chúng tôi bây giờ, chúng tôi đặt một ở đầu và bây giờ lập công thức tất cả các hoán vị có thể có của 0 và 1 trong chuỗi có độ dài L-1 vì vậy bằng cách lập công thức này, chúng ta lấy công thức của (L-1)! / (n-1)! * m! Ở đâu (n-1)! Là hoán vị của 1 còn lại và m! là hoán vị của số 0.
Kết luận
Trong bài viết này, chúng tôi giải quyết một vấn đề để tìm số hoán vị duy nhất bắt đầu bằng 1 của chuỗi nhị phân bằng cách áp dụng một số tổ hợp và tạo công thức cho nó.
Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.