Problema
Usando os inteiros de 1 até n, calcule duas quantidades: primeiro, some os inteiros e eleve o resultado ao quadrado; separadamente, eleve cada inteiro ao quadrado e some esses quadrados. Retorne a primeira quantidade menos a segunda.
Implemente difference_of_squares(n).
Entrada
n: O último inteiro a ser incluído.
Saída
Retorne o quadrado da soma menos a soma dos quadrados.
Restrições
0 ≤ n ≤ 50.000. Para n = 0, ambas as somas são 0. Todos os valores necessários cabem em inteiros assinados de 64 bits.
Exemplos
Entrada:
n = 4
Saída esperada:
expected = 70Entrada:
long long n = 4;
Saída esperada:
long long expected = 70;Entrada:
long n = 4;
Saída esperada:
long expected = 70;Explicação
(1 + 2 + 3 + 4)² = 100. A soma dos quadrados é 1 + 4 + 9 + 16 = 30. Subtraindo: 100 − 30 = 70.
Entrada:
n = 1
Saída esperada:
expected = 0Entrada:
long long n = 1;
Saída esperada:
long long expected = 0;Entrada:
long n = 1;
Saída esperada:
long expected = 0;Explicação
Ambas as quantidades são iguais a 1, então a diferença é 0.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Você está comparando dois resumos do mesmo intervalo: um pela soma, o outro pelo quadrado antes de somar.
Dica 2
Use as fórmulas fechadas para soma de inteiros e soma de quadrados em vez de percorrer todos os valores.
Dica 3
Trate com cuidado o caso zero, já que as duas quantidades devem ser zero ali.
Complexidade esperada
tempo O(1), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.