Dado un entero X , la tarea es encontrar el valor máximo N tal que la suma de los primeros N números naturales no sea mayor que X.
Ejemplos:
Entrada: X = 5
Salida: 2
2 es el valor máximo posible de N porque para N = 3, la suma de la serie excederá a X,
es decir, 1 2 + 2 2 + 3 2 = 1 + 4 + 9 = 14Entrada: X = 25
Salida: 3
Solución simple : una solución simple es ejecutar un bucle desde 1 hasta el N máximo tal que S(N) ≤ X , donde S(N) es la suma de los cuadrados de los primeros N números naturales. La suma del cuadrado de los primeros N números naturales viene dada por la fórmula S(N) = N * (N + 1) * (2 * N + 1) / 6 . La complejidad temporal de este enfoque es O(N) .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
3
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Enfoque eficiente :
una solución eficiente es usar la búsqueda binaria para encontrar el valor de N. La complejidad temporal de este enfoque es O(log N) .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
3
Complejidad de tiempo: O (logn)
Espacio Auxiliar: O(1)
Enfoque alternativo :
la idea es restar los cuadrados consecutivos de N mientras N>=(i*i) donde i comienza desde 1 y el ciclo termina cuando N<(i*i).
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
3
Complejidad de tiempo: O (sqrtn)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA