Valor mínimo de K tal que la suma de los cubos del primer número natural K es mayor que igual a N

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *