Find maximum N such that the sum of square of first N natural numbers is not more than X

0 0 10 minutes read

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. 1² + 2² + 3² = 1 + 4 + 9 = 14

Input: 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 numbers
int 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 X
int 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 code
int main()
{
    int X = 25;
    cout << findMaxN(X);
 
    return 0;
}
// This code is contributed by hemanth gadarla

Java

// Java implementation of the approach
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 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 approach
import math
 
# 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):
    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 code
X = 25
print(findMaxN(X))
 
# This code is contributed by souravmahato348.

C#

// C# implementation of the approach
using 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 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;
     
    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 numbers
function 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 X
function 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 code
let X = 25;
 
document.write(findMaxN(X));
 
// This code is contributed by rishavmahato348
 
</script>

Output

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 numbers
int 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 X
int 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 code
int main()
{
    int X = 25;
    cout << findMaxN(X);
 
    return 0;
}

Java

// Java implementation of the approach
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
    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 approach
using 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 numbers
function 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 X
function 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 numbers
function 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 X
function 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 Code
var X = 25;
 
document.write(findMaxN(X));
 
// This code is contributed by Ankita saini
 
</script>

Output

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 X
ll 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 code
int main()
{
    ll X = 25;
    cout << findMaxN(X);
 
    return 0;
}
// This code is contributed by hemanth gadarla

Java

// Java implementation of the approach
class 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 X
def 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 code
X = 25
print(findMaxN(X))
 
# This code is contributed by subhammahato348

C#

// C# implementation of the approach
using 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 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()
{
    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 X
function 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 code
var X = 25;
 
document.write(findMaxN(X));
 
// This code is contributed by noob2000
 
</script>

Output

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 zambiatek!