ধারণা
একটি প্রদত্ত পূর্ণসংখ্যা X এর সাপেক্ষে, আমাদের কাজ হল সর্বোচ্চ মান N নির্ধারণ করা যাতে প্রথম N প্রাকৃতিক সংখ্যার যোগফল X এর বেশি না হয়।
ইনপুট
X = 7
আউটপুট
2
2 হল N-এর সর্বাধিক সম্ভাব্য মান কারণ N =3-এর জন্য, সিরিজের যোগফল Xi.e-কে ছাড়িয়ে যাবে। 1^2 + 2^2 + 3^2 =1 + 4 + 9 =14
ইনপুট
X = 27
আউটপুট
3
3 হল N-এর সর্বাধিক সম্ভাব্য মান কারণ N =4-এর জন্য, সিরিজের যোগফল Xi.e-কে ছাড়িয়ে যাবে। 1^2 + 2^2 + 3^2 + 4^2 =1 + 4 + 9 + 16 =30
পদ্ধতি
সহজ সমাধান − এখানে, একটি সহজ সমাধান হল 1 থেকে সর্বোচ্চ N পর্যন্ত একটি লুপ চালানো যাতে S(N) ≤ X, এই ক্ষেত্রে S(N) কে প্রথম N প্রাকৃতিক সংখ্যার বর্গক্ষেত্রের সমষ্টি হিসাবে আখ্যায়িত করা হয়। এর ফলস্বরূপ, প্রথম N প্রাকৃতিক সংখ্যাগুলির বর্গক্ষেত্রের যোগফল S(N) =N * (N + 1) * (2 * N + 1) / 6 সূত্র দ্বারা দেওয়া হয়।
এটি উল্লেখ করা উচিত যে এই পদ্ধতির সময় জটিলতা হল O(N).
দক্ষ পদ্ধতি − আমরা অন্য একটি দক্ষ সমাধান বাস্তবায়ন করতে পারি যা বাইনারি অনুসন্ধান পদ্ধতির উপর ভিত্তি করে।
আমরা নিচের অ্যালগরিদম অনুসরণ করি যা ধাপে ধাপে ব্যাখ্যা করা হয়েছে −
-
বড় অ্যারেতে বাইনারি অনুসন্ধান শুরু করুন এবং মাঝামাঝি (নিম্ন + উচ্চ) / 2
হিসাবে পান -
এটা দেখা গেছে যে যদি উভয় অ্যারের থেকে মান একই হয় তবে উপাদানটি অবশ্যই ডান অংশে সোমার্ক কম মধ্যম হতে হবে
-
অন্যথায় এলিমেন্টের মাঝামাঝি হিসেবে উচ্চ চিহ্নিত করুন যদি মাঝারি উপাদান একই না হয় তাহলে বড় অ্যারের বাম অংশে থাকতে হবে।
এটা উল্লেখ করা উচিত যে এই পদ্ধতির সময় জটিলতা হল O(log N).
উদাহরণ
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Shows function to return the sum of the squares
// of first N1 natural numbers
ll squareSum(ll N1){
ll sum1 = (ll)(N1 * (N1 + 1) * (2 * N1 + 1)) / 6;
return sum1;
}
// Shows function to return the maximum N such that
// the sum of the squares of first N
// natural numbers is not more than X
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;
}
// Driver code
int main(){
ll X = 27;
cout << findMaxN(X);
return 0;
} আউটপুট
3
