अवधारणा
किसी दिए गए पूर्णांक X के संबंध में, हमारा कार्य अधिकतम मान N निर्धारित करना है ताकि पहली N प्राकृतिक संख्याओं का योग X से अधिक न हो।
इनपुट
X = 7
आउटपुट
2
2 N का अधिकतम संभव मान है क्योंकि N =3 के लिए, श्रृंखला का योग Xi से अधिक होगा। 1^2 + 2^2 + 3^2 =1 + 4 + 9 =14
इनपुट
X = 27
आउटपुट
3
3 N का अधिकतम संभव मान है क्योंकि N =4 के लिए, श्रृंखला का योग Xi से अधिक होगा। 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.
द्वारा दिया जाता है।यह ध्यान दिया जाना चाहिए कि इस दृष्टिकोण की समय जटिलता ओ (एन) है।
कुशल दृष्टिकोण - हम एक और कुशल समाधान लागू कर सकते हैं जो द्विआधारी खोज दृष्टिकोण पर आधारित है।
हम नीचे दिए गए एल्गोरिथम का अनुसरण करते हैं जिसे चरण दर चरण समझाया गया है -
-
बड़ी सरणी में द्विआधारी खोज शुरू करें और मध्य (निम्न + उच्च) / 2 के रूप में प्राप्त करें
-
यह देखा गया है कि यदि दोनों सरणी से मान समान है तो तत्व सही भाग में होना चाहिए, मध्य के रूप में कम होना चाहिए
-
अन्यथा उच्च को मध्य के रूप में चिह्नित करें क्योंकि यदि मध्य तत्व समान नहीं हैं तो तत्व बड़े सरणी के बाएं भाग में होना चाहिए।
यह ध्यान दिया जाना चाहिए कि इस दृष्टिकोण की समय जटिलता ओ (लॉग एन) है।
उदाहरण
// 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