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