Dado un entero positivo X (1 ≤ X ≤ 10 6 ) , la tarea es encontrar el valor mínimo N , tal que la suma de los primeros N números naturales sea ≥ X .
Ejemplos:
Entrada: X = 14
Salida: 5
Explicación: La suma de los primeros 5 números naturales es 15, que es mayor que X( = 14).
- 1 + 2 = 3 (<14)
- 1 + 2 + 3 = 6 (<14)
- 1 + 2 + 3 + 4 = 10 ( < 15)
- 1 + 2 + 3 + 4 + 5 = 15( > 14)
Entrada: X = 91
Salida: 13
Enfoque ingenuo: el enfoque más simple para resolver este problema es verificar cada valor en el rango [1, X] y devolver el primer valor de este rango para el cual se encuentra que la suma de los primeros N números naturales es ≥ X .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if sum of first // N natural numbers is >= X bool isGreaterEqual(int N, int X) { return (N * 1LL * (N + 1) / 2) >= X; } // Finds minimum value of // N such that sum of first // N natural number >= X int minimumPossible(int X) { for (int i = 1; i <= X; i++) { // Check if sum of first i // natural number >= X if (isGreaterEqual(i, X)) return i; } } // Driver Code int main() { // Input int X = 14; // Finds minimum value of // N such that sum of first // N natural number >= X cout << minimumPossible(X); return 0; }
Java
// Java Program to implement // the above approach import java.io.*; class GFG { // Function to check if sum of first // N natural numbers is >= X static boolean isGreaterEqual(int N, int X) { return (N * (N + 1) / 2) >= X; } // Finds minimum value of // N such that sum of first // N natural number >= X static int minimumPossible(int X) { for (int i = 1; i <= X; i++) { // Check if sum of first i // natural number >= X if (isGreaterEqual(i, X)) return i; } return 0; } // Driver Code public static void main (String[] args) { // Input int X = 14; // Finds minimum value of // N such that sum of first // N natural number >= X System.out.print(minimumPossible(X)); } } // This code is contributed by Dharanendra L V.
Python3
# Python3 Program to implement # the above approach # Function to check if sum of first # N natural numbers is >= X def isGreaterEqual(N, X): return (N * (N + 1) // 2) >= X # Finds minimum value of # N such that sum of first # N natural number >= X def minimumPossible(X): for i in range(1, X + 1): # Check if sum of first i # natural number >= X if (isGreaterEqual(i, X)): return i # Driver Code if __name__ == '__main__': # Input X = 14 # Finds minimum value of # N such that sum of first # N natural number >= X print (minimumPossible(X)) # This code is contributed by mohit kumar 29.
C#
// C# Program to implement // the above approach using System; public class GFG { // Function to check if sum of first // N natural numbers is >= X static bool isGreaterEqual(int N, int X) { return (N * (N + 1) / 2) >= X; } // Finds minimum value of // N such that sum of first // N natural number >= X static int minimumPossible(int X) { for (int i = 1; i <= X; i++) { // Check if sum of first i // natural number >= X if (isGreaterEqual(i, X)) return i; } return 0; } // Driver Code static public void Main () { // Input int X = 14; // Finds minimum value of // N such that sum of first // N natural number >= X Console.Write(minimumPossible(X)); } } // This code is contributed by Dharanendra L V.
Javascript
<script> // Javascript program to implement // the above approach // Function to check if sum of first // N natural numbers is >= X function isGreaterEqual(N, X) { return parseInt((N * (N + 1)) / 2) >= X; } // Finds minimum value of // N such that sum of first // N natural number >= X function minimumPossible(X) { for(let i = 1; i <= X; i++) { // Check if sum of first i // natural number >= X if (isGreaterEqual(i, X)) return i; } } // Driver Code // Input let X = 14; // Finds minimum value of // N such that sum of first // N natural number >= X document.write(minimumPossible(X)); // This code is contributed by rishavmahato348 </script>
5
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Método eficiente: a continuación se muestra la implementación del enfoque anterior:
- La idea es utilizar la búsqueda binaria para resolver este problema.
- Inicialice las variables bajo = 1, alto = X y realice una búsqueda binaria en este rango.
- Calcule mid = low + (high – low) / 2 y verifique si la suma de los primeros números medios es mayor o igual que x o no.
- Si sum ≥ X , guárdelo en una res variable y establezca high = mid-1
- De lo contrario, establecer bajo = medio + 1
- Imprimir res, que es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h> using namespace std; // Function to check if sum of first // N natural numbers is >= X bool isGreaterEqual(int N, int X) { return (N * 1LL * (N + 1) / 2) >= X; } // Finds minimum value of // N such that sum of first // N natural number >= X int minimumPossible(int X) { int low = 1, high = X, res = -1; // Binary Search while (low <= high) { int mid = low + (high - low) / 2; // Checks if sum of first 'mid' natural // numbers is greater than equal to X if (isGreaterEqual(mid, X)) { // Update res res = mid; // Update high high = mid - 1; } else // Update low low = mid + 1; } return res; } // Driver Code int main() { // Input int X = 14; // Finds minimum value of // N such that sum of first // N natural number >= X cout << minimumPossible(X); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if sum of first // N natural numbers is >= X static boolean isGreaterEqual(int N, int X) { return (N * (N + 1) / 2) >= X; } // Finds minimum value of // N such that sum of first // N natural number >= X static int minimumPossible(int X) { int low = 1, high = X, res = -1; // Binary Search while (low <= high) { int mid = low + (high - low) / 2; // Checks if sum of first 'mid' natural // numbers is greater than equal to X if (isGreaterEqual(mid, X)) { // Update res res = mid; // Update high high = mid - 1; } else // Update low low = mid + 1; } return res; } // Driver Code public static void main(String[] args) { // Input int X = 14; // Finds minimum value of // N such that sum of first // N natural number >= X System.out.print( minimumPossible(X)); } } // This code is contributed by code_hunt.
Python3
# Function to check if sum of first # N natural numbers is >= X def isGreaterEqual(N, X): return (N * (N + 1) // 2) >= X; # Finds minimum value of # N such that sum of first # N natural number >= X def minimumPossible(X): low = 1 high = X res = -1; # Binary Search while (low <= high): mid = low + (high - low) // 2; # Checks if sum of first 'mid' natural # numbers is greater than equal to X if (isGreaterEqual(mid, X)): # Update res res = mid; # Update high high = mid - 1; else: # Update low low = mid + 1; return res # Driver Code if __name__ == "__main__": # Input X = 14; # Finds minimum value of # N such that sum of first # N natural number >= X print(minimumPossible(X)); # This code is contributed by chitranayal.
C#
// C# program for the above approach using System; class GFG{ // Function to check if sum of first // N natural numbers is >= X static bool isGreaterEqual(int N, int X) { return (N * (N + 1) / 2) >= X; } // Finds minimum value of // N such that sum of first // N natural number >= X static int minimumPossible(int X) { int low = 1, high = X, res = -1; // Binary Search while (low <= high) { int mid = low + (high - low) / 2; // Checks if sum of first 'mid' natural // numbers is greater than equal to X if (isGreaterEqual(mid, X)) { // Update res res = mid; // Update high high = mid - 1; } else // Update low low = mid + 1; } return res; } // Driver Code static public void Main() { // Input int X = 14; // Finds minimum value of // N such that sum of first // N natural number >= X Console.Write( minimumPossible(X)); } } // This code is contributed by susmitakundugoaldanga.
Javascript
<script> // Function to check if sum of first // N natural numbers is >= X function isGreaterEqual(N, X) { return parseInt((N * (N + 1)) / 2) >= X; } // Finds minimum value of // N such that sum of first // N natural number >= X function minimumPossible(X) { let low = 1, high = X, res = -1; // Binary Search while (low <= high) { let mid = low + parseInt((high - low) / 2); // Checks if sum of first 'mid' natural // numbers is greater than equal to X if (isGreaterEqual(mid, X)) { // Update res res = mid; // Update high high = mid - 1; } else // Update low low = mid + 1; } return res; } // Driver Code // Input let X = 14; // Finds minimum value of // N such that sum of first // N natural number >= X document.write(minimumPossible(X)); // This code is contributed by rishavmahato348. </script>
5
Complejidad de tiempo: O(log(X))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA