প্রদত্ত সমস্যাটিতে, আমাদের 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 এর সংখ্যা গণনা করছি, আমরা একটিকে শুরুতে রাখি এবং এখন L-1 দৈর্ঘ্যের স্ট্রিংটিতে 0 এবং 1 এর সম্ভাব্য সমস্ত পারমুটেশন তৈরি করি তাই আমরা এটি তৈরি করে (L-1) এর সূত্র পান! /(n-1)! * মি! কোথায় (n-1)! বাকি 1 এর পারমুটেশন, এবং মি! 0 এর স্থানান্তর।
উপসংহার
এই নিবন্ধে, আমরা একটি বাইনারি স্ট্রিং এর 1 দিয়ে শুরু হওয়া অনন্য পারমুটেশনের সংখ্যা খুঁজে বের করার জন্য কিছু কম্বিনেটরিক্স প্রয়োগ করে এবং এর জন্য একটি সূত্র তৈরি করে একটি সমস্যার সমাধান করি।
আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে৷
