Dados dos enteros positivos X y K , la tarea es encontrar el valor mínimo de N posible tal que la suma de todos los números naturales del rango [K, N] sea al menos X . Si no existe ningún valor posible de N , imprima -1 .
Ejemplos:
Entrada: K = 5, X = 13
Salida: 7
Explicación: El valor mínimo posible es 7. Suma = 5 + 6 + 7 = 18, que es al menos 13.Entrada: K = 3, X = 15
Salida: 6
Enfoque ingenuo: el enfoque más simple para resolver este problema es verificar cada valor en el rango [K, X] y devolver el primer valor de este rango que tiene la suma de los primeros N números naturales al menos X .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum possible
// value of N such that sum of natural
// numbers from K to N is at least X
void minimumNumber(int K, int X)
{
// If K is greater than X
if (K > X) {
cout << "-1";
return;
}
// Stores value of minimum N
int ans = 0;
// Stores the sum of values
// over the range [K, ans]
int sum = 0;
// Iterate over the range [K, N]
for (int i = K; i <= X; i++) {
sum += i;
// Check if sum of first i
// natural numbers is >= X
if (sum >= X) {
ans = i;
break;
}
}
// Print the possible value of ans
cout << ans;
}
// Driver Code
int main()
{
int K = 5, X = 13;
minimumNumber(K, X);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the minimum possible
// value of N such that sum of natural
// numbers from K to N is at least X
static void minimumNumber(int K, int X)
{
// If K is greater than X
if (K > X)
{
System.out.println("-1");
return;
}
// Stores value of minimum N
int ans = 0;
// Stores the sum of values
// over the range [K, ans]
int sum = 0;
// Iterate over the range [K, N]
for(int i = K; i <= X; i++)
{
sum += i;
// Check if sum of first i
// natural numbers is >= X
if (sum >= X)
{
ans = i;
break;
}
}
// Print the possible value of ans
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
int K = 5, X = 13;
minimumNumber(K, X);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Function to find the minimum possible
# value of N such that sum of natural
# numbers from K to N is at least X
def minimumNumber(K, X):
# If K is greater than X
if (K > X):
print("-1")
return
# Stores value of minimum N
ans = 0
# Stores the sum of values
# over the range [K, ans]
sum = 0
# Iterate over the range [K, N]
for i in range(K, X + 1):
sum += i
# Check if sum of first i
# natural numbers is >= X
if (sum >= X):
ans = i
break
# Print the possible value of ans
print(ans)
# Driver Code
K = 5
X = 13
minimumNumber(K, X)
# This code is contributed by subham348
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum possible
// value of N such that sum of natural
// numbers from K to N is at least X
static void minimumNumber(int K, int X)
{
// If K is greater than X
if (K > X)
{
Console.Write("-1");
return;
}
// Stores value of minimum N
int ans = 0;
// Stores the sum of values
// over the range [K, ans]
int sum = 0;
// Iterate over the range [K, N]
for(int i = K; i <= X; i++)
{
sum += i;
// Check if sum of first i
// natural numbers is >= X
if (sum >= X)
{
ans = i;
break;
}
}
// Print the possible value of ans
Console.Write(ans);
}
// Driver Code
public static void Main()
{
int K = 5, X = 13;
minimumNumber(K, X);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum possible
// value of N such that sum of natural
// numbers from K to N is at least X
function minimumNumber(K, X)
{
// If K is greater than X
if (K > X) {
document.write("-1");
return;
}
// Stores value of minimum N
let ans = 0;
// Stores the sum of values
// over the range [K, ans]
let sum = 0;
// Iterate over the range [K, N]
for (let i = K; i <= X; i++) {
sum += i;
// Check if sum of first i
// natural numbers is >= X
if (sum >= X) {
ans = i;
break;
}
}
// Print the possible value of ans
document.write(ans);
}
// Driver Code
let K = 5, X = 13;
minimumNumber(K, X);
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
7
Complejidad temporal: O(N – K)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la búsqueda binaria . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos res como -1 , para almacenar el valor más pequeño posible de N que satisfaga las condiciones dadas.
- Inicialice dos variables, digamos bajo como K y alto como X , y realice una búsqueda binaria en este rango realizando los siguientes pasos:
- Encuentre el valor de mid como low + (high – low) / 2 .
- Si la suma de los números naturales de K a mid es mayor o igual a X o no.
- Si se determina que es cierto, actualice res como mid y configure high = (mid – 1) . De lo contrario, actualice el bajo a (medio + 1) .
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the sum of
// natural numbers from K to N is >= X
bool isGreaterEqual(int N, int K, int X)
{
return ((N * 1LL * (N + 1) / 2)
- ((K - 1) * 1LL * K / 2))
>= X;
}
// Function to find the minimum value
// of N such that the sum of natural
// numbers from K to N is at least X
void minimumNumber(int K, int X)
{
// If K is greater than X
if (K > X) {
cout << "-1";
return;
}
int low = K, high = X, res = -1;
// Perform the Binary Search
while (low <= high) {
int mid = low + (high - low) / 2;
// If the sum of the natural
// numbers from K to mid is atleast X
if (isGreaterEqual(mid, K, X)) {
// Update res
res = mid;
// Update high
high = mid - 1;
}
// Otherwise, update low
else
low = mid + 1;
}
// Print the value of
// res as the answer
cout << res;
}
// Driver Code
int main()
{
int K = 5, X = 13;
minimumNumber(K, X);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if the sum of
// natural numbers from K to N is >= X
static boolean isGreaterEqual(int N, int K, int X)
{
return ((N * 1L * (N + 1) / 2) -
((K - 1) * 1L * K / 2)) >= X;
}
// Function to find the minimum value
// of N such that the sum of natural
// numbers from K to N is at least X
static void minimumNumber(int K, int X)
{
// If K is greater than X
if (K > X)
{
System.out.println("-1");
return;
}
int low = K, high = X, res = -1;
// Perform the Binary Search
while (low <= high)
{
int mid = low + (high - low) / 2;
// If the sum of the natural
// numbers from K to mid is atleast X
if (isGreaterEqual(mid, K, X))
{
// Update res
res = mid;
// Update high
high = mid - 1;
}
// Otherwise, update low
else
low = mid + 1;
}
// Print the value of
// res as the answer
System.out.println(res);
}
// Driver Code
public static void main(String[] args)
{
int K = 5, X = 13;
minimumNumber(K, X);
}
}
// This code is contributed by Kingash
Python3
# Python program for the above approach
# Function to check if the sum of
# natural numbers from K to N is >= X
def isGreaterEqual(N, K, X):
return (((N * (N + 1) // 2)
- ((K - 1) * K // 2))
>= X)
# Function to find the minimum value
# of N such that the sum of natural
# numbers from K to N is at least X
def minimumNumber(K, X):
# If K is greater than X
if (K > X):
print("-1")
return
low = K
high = X
res = -1
# Perform the Binary Search
while (low <= high):
mid = low + ((high - low) // 2)
# If the sum of the natural
# numbers from K to mid is atleast X
if (isGreaterEqual(mid, K, X)):
# Update res
res = mid
# Update high
high = mid - 1
# Otherwise, update low
else:
low = mid + 1
# Print the value of
# res as the answer
print(res)
# Driver Code
K = 5
X = 13
minimumNumber(K, X)
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if the sum of
// natural numbers from K to N is >= X
static bool isGreaterEqual(int N, int K, int X)
{
return ((N * 1L * (N + 1) / 2) -
((K - 1) * 1L * K / 2)) >= X;
}
// Function to find the minimum value
// of N such that the sum of natural
// numbers from K to N is at least X
static void minimumNumber(int K, int X)
{
// If K is greater than X
if (K > X)
{
Console.Write("-1");
return;
}
int low = K, high = X, res = -1;
// Perform the Binary Search
while (low <= high)
{
int mid = low + (high - low) / 2;
// If the sum of the natural
// numbers from K to mid is atleast X
if (isGreaterEqual(mid, K, X))
{
// Update res
res = mid;
// Update high
high = mid - 1;
}
// Otherwise, update low
else
low = mid + 1;
}
// Print the value of
// res as the answer
Console.WriteLine(res);
}
// Driver Code
public static void Main()
{
int K = 5, X = 13;
minimumNumber(K, X);
}
}
// This code is contributed by subham348
Javascript
<script>
// Javascript program for the above approach
// Function to check if the sum of
// natural numbers from K to N is >= X
function isGreaterEqual(N, K, X)
{
return ((N * parseInt((N + 1) / 2))
- ((K - 1) * parseInt(K / 2)))
>= X;
}
// Function to find the minimum value
// of N such that the sum of natural
// numbers from K to N is at least X
function minimumNumber(K, X)
{
// If K is greater than X
if (K > X) {
document.write("-1");
return;
}
let low = K, high = X, res = -1;
// Perform the Binary Search
while (low <= high) {
let mid = low + parseInt((high - low) / 2);
// If the sum of the natural
// numbers from K to mid is atleast X
if (isGreaterEqual(mid, K, X)) {
// Update res
res = mid;
// Update high
high = mid - 1;
}
// Otherwise, update low
else
low = mid + 1;
}
// Print the value of
// res as the answer
document.write(res);
}
// Driver Code
let K = 5, X = 13;
minimumNumber(K, X);
// This code is contributed by subham348.
</script>
Producción:
7
Complejidad de tiempo: O(log(X – K))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA