Dado un número N , la tarea es encontrar el valor mínimo K tal que la suma de los cubos del primer número natural K sea mayor o igual que N .
Ejemplos:
Entrada: N = 100
Salida: 4
Explicación:
La suma de los cubos de los 4 primeros números naturales es 100, que es igual a N = 100
Entrada: N = 15
Salida: 3
Explicación:
La suma de los cubos de los 2 primeros números naturales es 9, que es menor que K = 15 y la suma de los primeros
3 números naturales es 36, que es mayor que K. Entonces, la respuesta es 3.
Enfoque ingenuo: el enfoque ingenuo para este problema es ejecutar un bucle y encontrar la suma de los cubos. Siempre que la suma exceda el valor de N, rompa el bucle.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
#include <bits/stdc++.h>
using namespace std;
// Function to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
int naive_find_x(int N)
{
// Variable to store the
// sum of cubes
int c = 0, i;
// Loop to find the number
// K
for(i = 1; i < N; i++)
{
c += i * i * i;
// If C is just greater then
// N, then break the loop
if (c >= N)
break;
}
return i;
}
// Driver code
int main()
{
int N = 100;
cout << naive_find_x(N);
return 0;
}
// This code is contributed by sapnasingh4991
Java
// Java program to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
class GFG {
// Function to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
static int naive_find_x(int N)
{
// Variable to store the
// sum of cubes
int c = 0, i;
// Loop to find the number
// K
for(i = 1; i < N; i++)
{
c += i * i * i;
// If C is just greater then
// N, then break the loop
if (c >= N)
break;
}
return i;
}
// Driver code
public static void main(String[] args)
{
int N = 100;
System.out.println(naive_find_x(N));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program to determine the # minimum value of K such that the # sum of cubes of first K # natural number is greater than # or equal to N # Function to determine the # minimum value of K such that the # sum of cubes of first K # natural number is greater than # or equal to N def naive_find_x(N): # Variable to store the # sum of cubes c = 0 # Loop to find the number # K for i in range(1, N): c += i*i*i # If C is just greater then # N, then break the loop if c>= N: break return i # Driver code if __name__ == "__main__": N = 100 print(naive_find_x(N))
C#
// C# program to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
using System;
class GFG {
// Function to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
static int naive_find_x(int N)
{
// Variable to store the
// sum of cubes
int c = 0, i;
// Loop to find the number
// K
for(i = 1; i < N; i++)
{
c += i * i * i;
// If C is just greater then
// N, then break the loop
if (c >= N)
break;
}
return i;
}
// Driver code
public static void Main(String[] args)
{
int N = 100;
Console.WriteLine(naive_find_x(N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
// Function to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
function naive_find_x(N)
{
// Variable to store the
// sum of cubes
var c = 0, i;
// Loop to find the number
// K
for(i = 1; i < N; i++)
{
c += i * i * i;
// If C is just greater then
// N, then break the loop
if (c >= N)
break;
}
return i;
}
// Driver code
var N = 100;
document.write(naive_find_x(N));
// This code is contributed by Amit Katiyar
</script>
Producción:
4
Complejidad de tiempo: O(K), donde K es el número que se necesita encontrar.
Enfoque eficiente: una observación que debe hacerse es que la suma de los primeros N números naturales al cubo viene dada por la fórmula:
sum = ((N * (N + 1))/2)2
Y, esta es una función monótonamente creciente. Por lo tanto, la idea es aplicar la búsqueda binaria para encontrar el valor de K. Si la suma es mayor que N para algún número ‘i’, entonces sabemos que la respuesta es menor o igual que ‘i’. Entonces, iterar a la mitad izquierda. De lo contrario, iterar a través de la mitad derecha.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to determine the
// minimum value of K such that
// the sum of cubes of first K
// natural number is greater than
// or equal to N
#include <bits/stdc++.h>
using namespace std;
// Function to determine the
// minimum value of K such that
// the sum of cubes of first K
// natural number is greater than
// or equal to N
int binary_searched_find_x(int k)
{
// Left bound
int l = 0;
// Right bound
int r = k;
// Variable to store the
// answer
int ans = 0;
// Applying binary search
while (l <= r)
{
// Calculating mid value
// of the range
int mid = l + (r - l) / 2;
if (pow(((mid * (mid + 1)) / 2), 2) >= k)
{
// If the sum of cubes of
// first mid natural numbers
// is greater than equal to N
// iterate the left half
ans = mid;
r = mid - 1;
}
else
{
// Sum of cubes of first
// mid natural numbers is
// less than N, then move
// to the right segment
l = mid + 1;
}
}
return ans;
}
// Driver code
int main()
{
int N = 100;
cout << binary_searched_find_x(N);
return 0;
}
// This code is contributed by shubhamsingh10
Java
// Java program to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
class GFG{
// Function to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
static int binary_searched_find_x(int k)
{
// Left bound
int l = 0;
// Right bound
int r = k;
// Variable to store the
// answer
int ans = 0;
// Applying binary search
while (l <= r)
{
// Calculating mid value
// of the range
int mid = l + (r - l) / 2;
if (Math.pow(((mid * (mid + 1)) / 2), 2) >= k)
{
// If the sum of cubes of
// first mid natural numbers
// is greater than equal to N
// iterate the left half
ans = mid;
r = mid - 1;
}
else
{
// Sum of cubes of first
// mid natural numbers is
// less than N, then move
// to the right segment
l = mid + 1;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 100;
System.out.println(binary_searched_find_x(N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program to determine the # minimum value of K such that the # sum of cubes of first K # natural number is greater than # or equal to N # Function to determine the # minimum value of K such that the # sum of cubes of first K # natural number is greater than # or equal to N def binary_searched_find_x(k): # Left bound l = 0 # Right bound r = k # Variable to store the # answer ans = 0 # Applying binary search while l<= r: # Calculating mid value # of the range mid = l+(r-l)//2 if ((mid*(mid + 1))//2)**2>= k: # If the sum of cubes of # first mid natural numbers # is greater than equal to N # iterate the left half ans = mid r = mid-1 else: # Sum of cubes of first # mid natural numbers is # less than N, then move # to the right segment l = mid + 1 return ans # Driver code if __name__ == "__main__": N = 100 print(binary_searched_find_x(N))
C#
// C# program to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
using System;
class GFG{
// Function to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
static int binary_searched_find_x(int k)
{
// Left bound
int l = 0;
// Right bound
int r = k;
// Variable to store the
// answer
int ans = 0;
// Applying binary search
while (l <= r)
{
// Calculating mid value
// of the range
int mid = l + (r - l) / 2;
if (Math.Pow(((mid * (mid + 1)) / 2), 2) >= k)
{
// If the sum of cubes of
// first mid natural numbers
// is greater than equal to N
// iterate the left half
ans = mid;
r = mid - 1;
}
else
{
// Sum of cubes of first
// mid natural numbers is
// less than N, then move
// to the right segment
l = mid + 1;
}
}
return ans;
}
// Driver code
public static void Main()
{
int N = 100;
Console.Write(binary_searched_find_x(N));
}
}
// This code is contributed by Nidhi_biet
Javascript
<script>
// javascript program to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
// Function to determine the
// minimum value of K such that the
// sum of cubes of first K
// natural number is greater than
// or equal to N
function binary_searched_find_x(k)
{
// Left bound
var l = 0;
// Right bound
var r = k;
// Variable to store the
// answer
var ans = 0;
// Applying binary search
while (l <= r)
{
// Calculating mid value
// of the range
var mid = parseInt(l + (r - l) / 2);
if (Math.pow(((mid * (mid + 1)) / 2), 2) >= k)
{
// If the sum of cubes of
// first mid natural numbers
// is greater than equal to N
// iterate the left half
ans = mid;
r = mid - 1;
}
else
{
// Sum of cubes of first
// mid natural numbers is
// less than N, then move
// to the right segment
l = mid + 1;
}
}
return ans;
}
// Driver code
var N = 100;
document.write(binary_searched_find_x(N));
// This code contributed by shikhasingrajput
</script>
Producción:
4
Complejidad temporal: O(log(K)).
Publicación traducida automáticamente
Artículo escrito por pedastrian y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA