Tutorialspoint.dev

Square pyramidal number (Sum of Squares)

A Square pyramidal number represents sum of squares of first natural numbers. First few Square pyramidal numbers are 1, 5, 14, 30, 55, 91, 140, 204, 285, 385, 506, …

Geometrically these numbers represent number of spheres to be stacked to form a pyramid with square base. Please see this Wiki image for more clarity.

Given a number s (1 <= s <= 1000000000). If s is sum of the squares of the first n natural numbers then print n, otherwise print -1.




Examples :

Input : 14
Output : 3
Explanation : 1*1 + 2*2 + 3*3 = 14

Input : 26
Output : -1

A simple solution is to run through all numbers starting from 1, compute current sum. If current sum is equal to given sum, then we return true, else false.

C++

// C++ program to check if a 
// given number is sum of 
// squares of natural numbers.
#include <iostream>
using namespace std;
  
// Function to find if the 
// given number is sum of 
// the squares of first n
// natural numbers
int findS(int s)
{
    int sum = 0;
  
    // Start adding squares of
    // the numbers from 1
    for (int n = 1; sum < s; n++) 
    {
        sum += n * n;
  
        // If sum becomes equal to s
        // return n
        if (sum == s)
            return n;
    }
  
    return -1;
}
  
// Drivers code
int main()
{
    int s = 13;
    int n = findS(s);
    n == -1 ? cout << "-1" : cout << n;
  
    return 0;
}

Java

// Java program to check if a 
// given number is sum of 
// squares of natural numbers.
class GFG 
{
  
    // Function to find if the 
    // given number is sum of 
    // the squares of first 
    // n natural numbers
    static int findS(int s)
    {
        int sum = 0;
  
        // Start adding squares of 
        // the numbers from 1
        for (int n = 1; sum < s; n++) 
        {
            sum += n * n;
  
            // If sum becomes equal to s
            // return n
            if (sum == s)
                return n;
        }
  
        return -1;
    }
  
    // Drivers code
    public static void main(String[] args)
    {
  
        int s = 13;
        int n = findS(s);
        if (n == -1)
            System.out.println("-1");
        else
            System.out.println(n);
    }
}

/div>

Python3

# Python3 program to find if
# the given number is sum of 
# the squares of first 
# n natural numbers
  
# Function to find if the given 
# number is sum of the squares 
# of first n natural numbers
def findS (s):
    _sum = 0
    n = 1
      
    # Start adding squares of
    # the numbers from 1
    while(_sum < s):
        _sum += n * n
        n+= 1
    n-= 1
      
    # If sum becomes equal to s
    # return n
    if _sum == s:
        return n
    return -1
  
# Driver code
s = 13
n = findS (s)
if n == -1:
    print("-1")
else:
    print(n)

C#

// C# program to check if a given 
// number is sum of squares of 
// natural numbers.
using System;
  
class GFG 
{
      
    // Function to find if the given
    // number is sum of the squares 
    // of first n natural numbers
    static int findS(int s)
    {
        int sum = 0;
      
        // Start adding squares of 
        // the numbers from 1
        for (int n = 1; sum < s; n++)
        {
            sum += n * n;
      
            // If sum becomes equal 
            // to s return n
            if (sum == s)
                return n;
        }
      
        return -1;
    }
      
    // Drivers code
    public static void Main()
    {
        int s = 13;
          
        int n = findS(s);
          
        if(n == -1)
            Console.Write("-1") ;
        else
            Console.Write(n);
    }
}
// This code is contribute by
// Smitha Dinesh Semwal

PHP

<?php
// PHP program to check if a 
// given number is sum of 
// squares of natural numbers.
  
// Function to find if the given number
// is sum of the squares of first n
// natural numbers
function findS($s)
{
    $sum = 0;
  
    // Start adding squares of
    // the numbers from 1
    for ($n = 1; $sum < $s; $n++) 
    {
        $sum += $n * $n;
  
        // If sum becomes equal to s
        // return n
        if ($sum == $s)
            return $n;
    }
  
    return -1;
}
  
// Drivers code
$s = 13;
$n = findS($s);
if($n == -1) 
    echo("-1");
else
    echo($n);
  
// This code is contributed by Ajit.
?>


OUTPUT :

-1

An alternate solution is to use Newton Raphson Method.
We know sum of squares of first n natural numbers is n * (n + 1) * (2*n + 1) / 6.

We can write solutions as

k * (k + 1) * (2*k + 1) / 6 = s

k * (k + 1) * (2*k + 1) – 6s = 0

We can find roots of above cubic equation using Newton Raphson Method, then check if root is integer or not.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter