Problema
O n-ésimo número triangular é 1 + 2 + … + n. Uma fórmula evita percorrer entradas muito grandes. O número triangular de ordem 0 é 0.
Implemente triangular_number(n).
Entrada
n: Um inteiro não negativo.
Saída
Retorne 1 + 2 + … + n.
Restrições
0 ≤ n ≤ 1.000.000.000. O resultado cabe em um inteiro assinado de 64 bits.
Exemplos
Entrada:
n = 10
Saída esperada:
expected = 55
Entrada:
long long n = 10;
Saída esperada:
long long expected = 55;
Entrada:
long n = 10;
Saída esperada:
long expected = 55;
Explicação
1 + 2 + … + 10 = 55.
Entrada:
n = 0
Saída esperada:
expected = 0
Entrada:
long long n = 0;
Saída esperada:
long long expected = 0;
Entrada:
long n = 0;
Saída esperada:
long expected = 0;
Explicação
Não há números para somar, então a soma é 0.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Procure um padrão nas somas acumuladas em vez de somar cada número um por um.
Dica 2
Use o atalho da progressão aritmética com o primeiro e o último termo, o que evita laço.
Dica 3
Tome cuidado com o caso 0 e garanta que sua aritmética caiba em 64 bits.
Complexidade esperada
O(1) tempo, O(1) espaço extra