Lo que deseas saber es el valor más pequeño de n
que cumpla la siguiente desigualdad.
1 + 2 + ... + n > k
para un determinado K
Esa sumatoria se puede expresar o calcular como:
1 + 2 + ... + n = n * (n+1) / 2
Por lo que tenemos,
n * (n+1) / 2 > k
n * (n+1) > 2 k
El problema se reduce a encontrar el n
más pequeño que satisface esta desigualdad.
Para ello, puedes aplicar fuerza bruta, el pseudocodigo seria algo asi:
n <- 0
Mientras n * (n+1) <= 2 * k Hacer
n <- n + 1
Fin Mientras
Escribir n
Hay una mejor forma de hacerlo en términos de eficiencia, y es aplicar una búsqueda binaria sobre el rango [0, INF]
, que permita encontrar el primer valor n
del rango tal que se cumpla la desigualdad. Esto funciona por el hecho de que si hacemos una función f(x)
que retorne true
si la desigualdad es cierta, o false
de lo contrario, entonces los resultados en un "arreglo" (donde la primera posición corresponde a n = 0, luego la siguiente n = 1, y así sucesivamente) seguirán el siguiente patrón:
[F, F, F, F, F, T, T, T, T, T, T]
, F para las valuaciones que son falsas y T para las que son verdaderas.
Podemos observar que el "arreglo" (la función) es apropiada para aplicar búsqueda binaria, en la medida que queremos encontrar el índice del primer T, dado que se encuentra ordenado.
l <- 0
r <- INF
Mientras l < r Hacer
n <- (l + r) / 2
sum <- n * (n + 1) / 2
Si suma > k Entonces
r <- n
Sino
l <- n + 1
FinSi
Fin Mientras
Escribir l