주어진 문제에서 0과 1로 구성된 문자열이 주어집니다. 문자열이 1로 시작하는 순열의 총 수를 찾아야 합니다. 답은 엄청나게 많을 수 있으므로 1000000007로 모드로 인쇄합니다.
Input : str ="10101001001" Output : 210 Input : str ="101110011" Output : 56
우리는 이 문제를 풀기 위해 몇 가지 조합을 적용하고 몇 가지 공식을 만들어 주어진 문제를 해결할 것입니다.
해결책을 찾기 위한 접근 방식
접근 방식에서 우리는 0과 1의 수를 계산할 것입니다. 이제 n이 문자열에 있는 1의 개수이고 m이 문자열에 있는 0의 개수라고 가정하고 L을 주어진 문자열의 길이라고 하자. 따라서 이 문제를 해결하기 위해 만든 공식은 (L-1 )!/ (n-1)! * 음!.
예시
#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;
} 출력
56
주어진 프로그램은 O(N)의 시간 복잡도를 가지며, 여기서 n은 주어진 문자열의 길이입니다.
위 코드 설명
이 접근 방식에서 우리는 이제 문자열 내부에 존재하는 1과 0의 수를 세고 있으며 시작 부분에 1을 배치하고 이제 길이 L-1의 문자열에서 0과 1의 가능한 모든 순열을 공식화하므로 이것을 공식화함으로써 우리는 (L-1)의 공식을 얻으십시오! / (n-1)! * 중! 어디(n-1)! 나머지 1과 m의 순열입니다! 0의 순열입니다.
결론
이 기사에서는 몇 가지 조합을 적용하고 이에 대한 공식을 만들어 이진 문자열의 1부터 시작하는 고유한 순열의 수를 찾는 문제를 해결합니다.
우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결한 완전한 접근 방식( Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.