Problema
El n-ésimo número triangular es 1 + 2 + … + n. Una fórmula evita iterar sobre entradas muy grandes. El número triangular 0 es 0.
Implementa triangular_number(n).
Entrada
n: Un entero no negativo.
Salida
Devuelve 1 + 2 + … + n.
Restricciones
0 ≤ n ≤ 1,000,000,000. El resultado cabe en un entero con signo de 64 bits.
Ejemplos
Entrada:
n = 10
Salida esperada:
expected = 55
Entrada:
long long n = 10;
Salida esperada:
long long expected = 55;
Entrada:
long n = 10;
Salida esperada:
long expected = 55;
Explicación
1 + 2 + … + 10 = 55.
Entrada:
n = 0
Salida esperada:
expected = 0
Entrada:
long long n = 0;
Salida esperada:
long long expected = 0;
Entrada:
long n = 0;
Salida esperada:
long expected = 0;
Explicación
No hay números para sumar, así que la suma es 0.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Busca un patrón en las sumas acumuladas en vez de añadir cada número uno por uno.
Pista 2
Usa el atajo de la serie aritmética basado en el primer y el último término, lo que evita recorrer un bucle.
Pista 3
Ten cuidado con el caso 0 y asegúrate de que tu aritmética no supere los límites de 64 bits.
Complejidad esperada
tiempo O(1), espacio extra O(1)