মনে করুন, একটি ধনাত্মক পূর্ণসংখ্যা n দেওয়া আছে। n-এর চেয়ে ছোট বা সমান অ-ঋণাত্মক পূর্ণসংখ্যাগুলোর মধ্যে যাদের বাইনারি রিপ্রেজেন্টেশনতে কনsekutিভ ১ নেই, তাদের সংখ্যা বের করতে হবে।
যেমন, n = 7 হলে, উত্তর ৫। কারণ ৫-এর বাইনারি 101।
সমাধানের ধাপসমূহ
- convert(n) ফাংশন: n-এর বাইনারি স্ট্রিং রিটার্ন করুন (LSB প্রথমে)
- bits := convert(num), n := bits.size()
- ones[n], zeroes[n] অ্যারে: ones[0]=zeroes[0]=1
- i := 1 থেকে n-1: zeroes[i] = zeroes[i-1]+ones[i-1], ones[i] = zeroes[i-1]
- ret := ones[n-1] + zeroes[n-1]
- i := n-2 থেকে ০ পর্যন্ত:
- যদি bits[i]=='0' এবং bits[i+1]=='0', ret -= ones[i]
- যদি bits[i]=='1' এবং bits[i+1]=='1', ব্রেক করুন
- ret রিটার্ন করুন
উদাহরণ
#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
