Given an integer X, the task is to find the maximum value N such that the sum of first N natural numbers is not more than X.
Examples:
Input: X = 5
Output: 2
2 is the maximum possible value of N because for N = 3, the sum of the series will exceed X
i.e. 12 + 22 + 32 = 1 + 4 + 9 = 14Input: X = 25
Output: 3
Simple Solution: A simple solution is to run a loop from 1 till the maximum N such that S(N) ? X, where S(N) is the sum of square of first N natural numbers. Sum of square of first N natural numbers is given by the formula S(N) = N * (N + 1) * (2 * N + 1) / 6. The time complexity of this approach is O(N).
Below is the implementation of the above approach :
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the sum of the squares// of first N natural numbersint squareSum(int N){ int sum = (int)(N * (N + 1) * (2 * N + 1)) / 6; return sum;}// Function to return the maximum N such that// the sum of the squares of first N// natural numbers is not more than Xint findMaxN(int X){ int N = sqrt(X); // Iterate till maxvalue of N for (int i = 1; i <= N; i++) { // If the condition fails then return the i-1 i.e // sum of squares till i-1 if (squareSum(i) > X) return i - 1; } return -1L;}// Driver codeint main(){ int X = 25; cout << findMaxN(X); return 0;}// This code is contributed by hemanth gadarla |
Java
// Java implementation of the approachclass GFG{ // Function to return the sum of the squares // of first N natural numbers static long squareSum(long N) { long sum = (long)(N * (N + 1) * (2 * N + 1)) / 6; return sum; } // Function to return the maximum N such that // the sum of the squares of first N // natural numbers is not more than X static long findMaxN(long X) { long N = (long)Math.sqrt(X); // Iterate through the maxvalue // of N and find the // ith position for (long i = 1; i <= N; i++) { if (squareSum(i) > X) return i - 1; } return -1; } // Driver code public static void main(String[] args) { long X = 25; System.out.println(findMaxN(X)); }}// This code contributed by Hemanth gadarla |
Python3
# Python implementation of the approachimport math# Function to return the sum of the squares# of first N natural numbersdef squareSum(N): sum = (N * (N + 1) * (2 * N + 1)) // 6 return sum# Function to return the maximum N such that# the sum of the squares of first N# natural numbers is not more than Xdef findMaxN(X): N = (int)(math.sqrt(X)) # Iterate till maxvalue of N for i in range(1, N + 1): # If the condition fails then return the i-1 i.e # sum of squares till i-1 if (squareSum(i) > X): return i - 1 return -1# Driver codeX = 25print(findMaxN(X))# This code is contributed by souravmahato348. |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the sum of the squares// of first N natural numbersstatic long squareSum(long N){ long sum = (long)(N * (N + 1) * (2 * N + 1)) / 6; return sum;}// Function to return the maximum N such that// the sum of the squares of first N// natural numbers is not more than Xstatic long findMaxN(long X){ long N = (long)Math.Sqrt(X); // Iterate through the maxvalue // of N and find the // ith position for(long i = 1; i <= N; i++) { if (squareSum(i) > X) return i - 1; } return -1;}// Driver codepublic static void Main(string[] args){ long X = 25; Console.WriteLine(findMaxN(X));}}// This code is contributed by ukasp |
Javascript
<script>// Javascript implementation of the approach// Function to return the sum of the squares// of first N natural numbersfunction squareSum(N){ let sum = parseInt((N * (N + 1) * (2 * N + 1)) / 6); return sum;}// Function to return the maximum N such that// the sum of the squares of first N// natural numbers is not more than Xfunction findMaxN(X){ let N = Math.sqrt(X); // Iterate till maxvalue of N for(let i = 1; i <= N; i++) { // If the condition fails then // return the i-1 i.e sum of // squares till i-1 if (squareSum(i) > X) return i - 1; } return -1;}// Driver codelet X = 25;document.write(findMaxN(X));// This code is contributed by rishavmahato348</script> |
Output
3
Time Complexity: O(n)
Auxiliary Space: O(1)
Efficient Approach:
An efficient solution is to use Binary Search to find the value of N. The time complexity of this approach is O(log N).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the sum of the squares// of first N natural numbersint squareSum(int N){ int sum = (int)(N * (N + 1) * (2 * N + 1)) / 6; return sum;}// Function to return the maximum N such that// the sum of the squares of first N// natural numbers is not more than Xint findMaxN(int X){ int low = 1, high = 100000; int N = 0; while (low <= high) { int mid = (high + low) / 2; if (squareSum(mid) <= X) { N = mid; low = mid + 1; } else high = mid - 1; } return N;}// Driver codeint main(){ int X = 25; cout << findMaxN(X); return 0;} |
Java
// Java implementation of the approachclass GFG { // Function to return the sum of the squares // of first N natural numbers static long squareSum(long N) { long sum = (long)(N * (N + 1) * (2 * N + 1)) / 6; return sum; } // Function to return the maximum N such that // the sum of the squares of first N // natural numbers is not more than X static long findMaxN(long X) { long low = 1, high = 100000; int N = 0; while (low <= high) { long mid = (high + low) / 2; if (squareSum(mid) <= X) { N = (int)mid; low = mid + 1; } else high = mid - 1; } return N; } // Driver code public static void main(String[] args) { long X = 25; System.out.println(findMaxN(X)); }}// This code contributed by Rajput-Ji |
C#
// C# implementation of the approachusing System;class GFG { // Function to return the sum of the squares // of first N natural numbers static long squareSum(long N) { long sum = (long)(N * (N + 1) * (2 * N + 1)) / 6; return sum; } // Function to return the maximum N such that // the sum of the squares of first N // natural numbers is not more than X static long findMaxN(long X) { long low = 1, high = 100000; int N = 0; while (low <= high) { long mid = (high + low) / 2; if (squareSum(mid) <= X) { N = (int)mid; low = mid + 1; } else high = mid - 1; } return N; } // Driver code static public void Main() { long X = 25; Console.WriteLine(findMaxN(X)); }}// This code contributed by ajit |
Python3
# Python3 implementation of the approach # Function to return the sum of the # squares of first N natural numbers def squareSum(N): Sum = (N * (N + 1) * (2 * N + 1)) // 6 return Sum# Function to return the maximum N such # that the sum of the squares of first N # natural numbers is not more than X def findMaxN(X): low, high, N = 1, 100000, 0 while low <= high: mid = (high + low) // 2 if squareSum(mid) <= X: N = mid low = mid + 1 else: high = mid - 1 return N # Driver code if __name__ == "__main__": X = 25 print(findMaxN(X)) # This code is contributed # by Rituraj Jain |
PHP
<?php// PHP implementation of the approach// Function to return the sum of the // squares of first N natural numbersfunction squareSum($N){ $sum = ($N * (int)($N + 1) * (2 * $N + 1)) / 6; return $sum;}// Function to return the maximum N such // that the sum of the squares of first N// natural numbers is not more than Xfunction findMaxN($X){ $low = 1; $high = 100000; $N = 0; while ($low <= $high) { $mid = (int)($high + $low) / 2; if (squareSum($mid) <= $X) { $N = $mid; $low = $mid + 1; } else $high = $mid - 1; } return $N;}// Driver code$X = 25;echo findMaxN($X);// This code is contributed by akt_mit?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the sum of the squares// of first N natural numbersfunction squareSum(N){ var sum = parseInt((N * (N + 1) * (2 * N + 1)) / 6); return sum;}// Function to return the maximum N such that// the sum of the squares of first N// natural numbers is not more than Xfunction findMaxN(X){ var low = 1, high = 100000; var N = 0; while (low <= high) { var mid = (high + low) / 2; if (squareSum(mid) <= X) { N = parseInt(mid); low = mid + 1; } else high = mid - 1; } return N;}// Driver Codevar X = 25;document.write(findMaxN(X));// This code is contributed by Ankita saini</script> |
Output
3
Time Complexity: O(logn)
Auxiliary Space: O(1)
Alternate Approach :
The idea is to subtract the consecutive squares from N while N>=(i*i) where i starts from 1 and loop ends when N<(i*i).
Below is the implementation of above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define ll long long// Function to return the maximum N such that// the sum of the squares of first N// natural numbers is not more than Xll findMaxN(ll X){ ll i = 1; // To keep track of all squares in the series ll count = 0; // to count the number of squares used to // reach N ll N = X; while (N >= (i * i)) { // Subtract the square of current number N -= (i * i); // Increment count count += 1; // increment i for next square number i += 1; } return count;}// Driver codeint main(){ ll X = 25; cout << findMaxN(X); return 0;}// This code is contributed by hemanth gadarla |
Java
// Java implementation of the approachclass GFG { // Function to return the maximum N such that // the sum of the squares of first N // natural numbers is not more than X static long findMaxN(long X) { long N = X; // To keep track of the squares of consecutive // numbers int i = 1; while (N >= (i * i)) { N -= (i * i); i += 1; } return i - 1; } // Driver code public static void main(String[] args) { long X = 25; System.out.println(findMaxN(X)); }}// This code contributed by Hemanth gadarla |
Python3
# Python3 implementation of the approach# Function to return the maximum N such that# the sum of the squares of first N# natural numbers is not more than Xdef findMaxN(X): # To keep track of all squares in the series i = 1 # To count the number of squares used to count = 0 # Reach N N = X while (N >= (i * i)): # Subtract the square of current number N -= (i * i) # Increment count count += 1 # increment i for next square number i += 1 return count# Driver codeX = 25print(findMaxN(X))# This code is contributed by subhammahato348 |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the maximum N such that// the sum of the squares of first N// natural numbers is not more than Xstatic long findMaxN(long X){ long N = X; // To keep track of the squares // of consecutive numbers int i = 1; while (N >= (i * i)) { N -= (i * i); i += 1; } return i - 1;}// Driver codepublic static void Main(){ long X = 25; Console.Write(findMaxN(X));}}// This code is contributed by subhammahato348 |
Javascript
<script>// Javascript implementation of the approach// Function to return the maximum N such that// the sum of the squares of first N// natural numbers is not more than Xfunction findMaxN(X){ // To keep track of all squares // in the series var i = 1; // To count the number of squares // used to reach N var count = 0; var N = X; while (N >= (i * i)) { // Subtract the square of current number N -= (i * i); // Increment count count += 1; // Increment i for next square number i += 1; } return count;}// Driver codevar X = 25;document.write(findMaxN(X));// This code is contributed by noob2000</script> |
Output
3
Time Complexity: O(sqrtn)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
