সমস্যা বিবরণ
একটি পূর্ণসংখ্যা X দেওয়া আছে। 0 থেকে X পর্যন্ত রূপান্তরের জন্য সর্বোচ্চ কত ধাপ লাগবে তা বের করতে হবে।
বৈধ রূপান্তর: একটি ধাপ গণনা হয় যখন A থেকে B-এ রূপান্তর হয়। শর্ত: A != B এবং A & B = A (এখানে & হলো বিটওয়াইজ AND)। ত есть 1 ধাপ হলো A থেকে B-এ রূপান্তর। 0 থেকে X পর্যন্ত সর্বোচ্চ ধাপ গণনা করতে হবে।
উদাহরণ
ইনপুট - X = 7
আউটপুট - 3
ব্যাখ্যা -
ধাপ ১: 0(00) থেকে 1(01), 0!=1 এবং 0&1=0, রূপান্তর 00=>01 ধাপ ২: 1(001) থেকে 3(011), 1!=3 এবং 1&3=1, রূপান্তর 001=>011 ধাপ ৩: 3(0011) থেকে 7(0111), 3!=7 এবং 3&7=3, রূপান্তর 0011=>0111
সমাধানের পদ্ধতি
X-এ সেট বিট (বিট যেগুলোর মান ১) সংখ্যা গণনা করলে 0 থেকে X পর্যন্ত সর্বোচ্চ রূপান্তর পাওয়া যায়। প্রতিটি সেট বিটের জন্য এক ধাপ করে রূপান্তর করলে সর্বোচ্চ ধাপ হয়। A থেকে B-এ রূপান্তরে A-র সেট বিটগুলো B-তে সেট থাকতে হবে, কিন্তু বিপরীত ضرুরী নয়। তাই ন্যূনতম রূপান্তর ১ হতে পারে (কারণ 0-তে কোনো সেট বিট নেই)।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int maxtransformation(int x) {
int steps = 0;
// সেট বিট গণনা
while (x) {
steps += x & 1;
x >>= 1;
}
return steps;
}
int main() {
int x = 7;
cout << "The maximum number of steps to transform 0 to " << x << " with bitwise AND are " << maxtransformation(x);
return 0;
}
আউটপুট
The maximum number of steps to transform 0 to 7 with bitwise AND are 3
