ধরুন আমাদের একটি ধনাত্মক পূর্ণসংখ্যা n আছে। আমাদের n-এর চেয়ে কম বা সমান অ-ঋণাত্মক পূর্ণসংখ্যা খুঁজে বের করতে হবে। সীমাবদ্ধতা হল বাইনারি উপস্থাপনা ধারাবাহিকভাবে ধারণ করবে না। তাই যদি ইনপুট 7 হয়, তাহলে উত্তর হবে 5, কারণ 5-এর বাইনারি উপস্থাপনা হল 101৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন রূপান্তর() সংজ্ঞায়িত করুন, এটি n, নেবে
- ret :=খালি স্ট্রিং
- যখন n অ-শূন্য, কর −
- ret :=ret + (n mod 2)
- n :=ডান শিফট n, 1 বার
- রিটার্ন রিটার্ন
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- বিটস :=ফাংশন রূপান্তর (সংখ্যা) কল করুন
- n :=বিটের আকার
- n আকারের একটি অ্যারে সংজ্ঞায়িত করুন, n আকারের একটি অ্যারের শূন্য সংজ্ঞায়িত করুন
- ones[0] :=1, zeroes[0] :=1
- আরম্ভ করার জন্য i :=1, যখন i
- শূন্য[i] :=শূন্য[i - 1] + ones[i - 1]
- ones[i] :=শূন্য[i - 1]
- করুন
- যদি বিট[i] '0' এর মতো হয় এবং বিট[i + 1] '0' এর মতো হয়, তাহলে −
- ret :=ret - ones[i]
- অন্যথায় যখন বিট[i] '1'-এর মতো এবং বিট[i + 1] '1'-এর মতো, তখন −
- লুপ থেকে বেরিয়ে আসুন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string convert(int n){
string ret = "";
while(n){
ret += (n % 2) + '0';
n >>= 1;
}
return ret;
}
int findIntegers(int num) {
string bits = convert(num);
int n = bits.size();
vector <int> ones(n);
vector <int> zeroes(n);
ones[0] = zeroes[0] = 1;
for(int i = 1; i < n; i++){
zeroes[i] = zeroes[i - 1] + ones[i - 1];
ones[i] = zeroes[i - 1];
}
int ret = ones[n - 1] + zeroes[n - 1];
for(int i = n - 2; i >= 0; i--){
if(bits[i] == '0' && bits[i + 1] == '0') ret -= ones[i];
else if(bits[i] == '1' && bits[i + 1]== '1') break;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findIntegers(7));
} ইনপুট
7
আউটপুট
5
