সমস্যা বিবরণ
দুটি মান x এবং y দেওয়া হয়েছে। আমাদের কাজ হল y mod (2^x) এর মান বের করা।
উদাহরণ
ইনপুট: x = 2, y = 19 আউটপুট: 3 ব্যাখ্যা: 19 % 2² = 19 % 4 = 3
সমাধানের পদ্ধতি
সাধারণ পদ্ধতিতে pow() ফাংশন দিয়ে 2^x বের করে মডুলাস নেওয়া যায়। কিন্তু বড় x-এর জন্য লগারিদম ও বিট অপারেশন দিয়ে অপ্টিমাইজ করা যায়।
- যদি log₂(y) < x হয়, তবে ফলাফল y।
- যদি x > 63 হয়, তবে ওভারফ্লো হওয়ায় ফলাফল y।
- অন্যথায় y % (1 << x) বের করা।
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
long long findModVal(long long y, int x) {
if (log2(y) < x) return y;
if (x > 63) return y;
return (y % (1LL << x));
}
int main() {
long long y = 82829;
int x = 12;
cout << "y mod 2^x এর মান: " << findModVal(y, x);
return 0;
}
আউটপুট
y mod 2^x এর মান: 909
