কনসেপ্ট
একটি পূর্ণসংখ্যা X দেওয়া আছে। প্রাকৃতিক সংখ্যার বর্গের যোগফল X-এ অতিক্রম না করে এমন সর্বোচ্চ মান N নির্ণয় করতে হবে।
ইনপুট ১
X = 7
আউটপুট ১
2
N = ৩ হলে বর্গের যোগফল ১² + ২² + ৩² = ১৪ যা ৭-এ বেশি। তাই সর্বোচ্চ N = ২।
ইনপুট ২
X = 27
আউটপুট ২
3
N = ৪ হলে বর্গের যোগফল ১² + ২² + ৩² + ৪² = ৩০ যা ২৭-এ বেশি। তাই সর্বোচ্চ N = ৩।
পদ্ধতি
সহজ সমাধান: ১ থেকে N পর্যন্ত লুপ চালিয়ে বর্গের যোগফল S(N) = N(N+1)(2N+1)/6 সূত্র দিয়ে যাচাই করুন। টাইম কমপ্লেক্সিটি O(N)।
দক্ষ সমাধান: বাইনারি সার্চ ব্যবহার করুন। লো (low) = ১, হাই (high) = ১০০০০০ ধরে মিড (mid) = (low+high)/2 নিয়ে S(mid) ≤ X কিনা যাচাই করুন। টাইম কমপ্লেক্সিটি O(log N)।
উদাহরণ (C++ কোড)
// C++ ইমপ্লিমেন্টেশন
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// প্রথম N প্রাকৃতিক সংখ্যার বর্গের যোগফল ফেরত দেওয়ার ফাংশন
ll squareSum(ll N1) {
ll sum1 = (ll)(N1 * (N1 + 1) * (2 * N1 + 1)) / 6;
return sum1;
}
// বর্গের যোগফল X-এ অধিক না হলে সর্বোচ্চ N ফেরত দেওয়ার ফাংশন
ll findMaxN(ll X) {
ll low1 = 1, high1 = 100000;
int N1 = 0;
while (low1 <= high1) {
ll mid1 = (high1 + low1) / 2;
if (squareSum(mid1) <= X) {
N1 = mid1;
low1 = mid1 + 1;
} else
high1 = mid1 - 1;
}
return N1;
}
// ড্রাইভার কোড
int main() {
ll X = 27;
cout << findMaxN(X);
return 0;
}
আউটপুট
3
