ধরুন আমাদের একটি বাইনারি স্ট্রিং S এবং একটি ধনাত্মক পূর্ণসংখ্যা N আছে, আমাদেরকে সত্য বলতে হবে যদি এবং শুধুমাত্র যদি 1 থেকে N পর্যন্ত প্রতিটি পূর্ণসংখ্যা X এর জন্য, X এর বাইনারি উপস্থাপনাটি প্রদত্ত S এর একটি সাবস্ট্রিং। তাই যদি S =“0110 ” এবং N =3, তাহলে ফলাফলটি সত্য হবে, কারণ 1, 10 এবং 11 সবই 0110 এ উপস্থিত রয়েছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
রূপান্তর করার একটি পদ্ধতি সংজ্ঞায়িত করুন(), যা n ইনপুট হিসাবে গ্রহণ করবে
-
ret :=একটি খালি স্ট্রিং
-
যখন n 0 নয়
-
ret :=ret concatenate n mod 2
-
n :=n / 2
-
-
রিভার্স রিট এবং রিটার্ন
-
মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন
-
i এর জন্য :=N, যখন i>=N/2, i কমিয়ে আনুন 1
-
temp :=রূপান্তর(i)
-
যদি তাপমাত্রা S-তে না থাকে, তাহলে মিথ্যা ফেরত দিন
-
-
প্রত্যাবর্তন সত্য।
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string convert(int n){
string ret = "";
while(n){
ret += (n % 2) + '0';
n /= 2;
}
reverse(ret.begin(), ret.end());
return ret;
}
bool queryString(string S, int N) {
for(int i = N; i >= N/2; i-- ){
string temp = convert(i);
if(S.find(temp) == string::npos) return false;
}
return true;
}
};
main(){
Solution ob;
cout << (ob.queryString("0110", 3));
} ইনপুট
"0110" 3
আউটপুট
1
