Soma de números ímpares do triângulo

Deixe um comentário / Algoritmo, Fácil, Puzzle / Por
Brown and Pink Keychain

Problema disponível em https://www.codewars.com/kata/55fd2d567d94ac3bc9000064

Dado um triângulo de números ímpares consecutivos, calcular a soma dos elementos da enésima linha.

             1
          3     5
       7     9    11
   13    15    17    19
21    23    25    27    29
Entrada: 1. Saída: 1
Entrada: 2. Saída: 8
Entrada: 3. Saída: 27

Neste problema, o objetivo é encontrar os elementos da linha n e calcular a soma desses valores. Podemos observar duas propriedades:

  • A primeira linha tem 1 elemento. A segunda tem 2. Concluíndo, a linha n tem n elementos. Como vamos somar n valores, a complexidade temporal desse algoritmo é no mínimo O(n), onde n é entrada. Será que é a forma mais eficiente? Vamos descobrir.
  • Se soubermos qual o primeiro elemento da linha n, sabemos todos os números da linha. Se o primeiro elemento da linha n for Qn, a saída dever ser:
Qn + (Qn + 1 * 2) + (Qn + 2 * 2) + ... + (Qn + (n-1) * 2)

Para calcular o primeiro elemento da linha n, há duas abordagens.

  • O primeiro elemento da primeira linha é 1. Da segunda linha é 3. Da terceira é 7. Da quarta é 13. Note que a segunda linha é o número da primeira mais 2. O número da terceira linha é o número da segunda linha mais 4. O número da quarta linha é o número da terceira mais 6. Por isso, seria possível ir somando os valores até chegar a linha n. A complexidade desse algoritmo é O(n), onde n é a entrada.
  • A segunda abordagem é mais eficiente. Se eu estou analisando a linha n e eu souber a quantidade de elementos até a linha (n-1), eu consigo descobrir o primeiro número da linha n. Observe a linha 3. Até a linha 2, há 3 elementos. O primeiro elemento da linha 3 será (3 * 2) + 1 = 7. Há 10 elementos até a linha 4. Por isso, o primeiro elemento da linha 5 é (10 * 2) + 1 = 21. O primeiro elemento da linha n é portanto:
Qn = quantidade_elementos_altura(n-1) * 2 + 1

Então, o nosso objetivo é descobrir quantos valores há em uma pirâmide de altura Hn. 

Altura => Elementos
1 => 1 elemento = 1
2 => 3 elementos = 1 + 2
3 => 6 elementos = 1 + 2 + 3
4 => 10 elementos = 1 + 2 + 3 + 4
  • A quantidade de elementos de cada linha segue uma progressão aritmética, onde o valor inicial é 1 e razão 1. Por isso, podemos usar a fórmula da soma de uma PA:
Hn = (a1 + an) * n / 2
an = a1 + (n - 1) * r
r = 1
a1 = 1

Hn = (1 + 1 + (n - 1) * 1) * n / 2
Hn = (n + 1) * n / 2

Portanto, o primeiro elemento da linha n é Qn:

Qn = quantidade_elementos_altura(n-1) * 2 + 1
Qn = Hn-1 * 2 + 1
Qn = ((n - 1) + 1) * (n - 1) / 2 * 2 + 1
Qn = n * (n - 1) + 1

Para conferir:

Q4 = 4 * (4 - 1) + 1 = 4 * 3 + 1 = 13
Q5 = 5 * (5 - 1) + 1 = 5 * 4 + 1 = 21

Logo, sabendo o Qn, conseguimos calcular facilmente a soma dos elementos da linha. Note entretanto o seguinte: 

Output = Qn + (Qn + 1 * 2) + (Qn + 2 * 2) + ... + (Qn + (n - 1) * 2)
Output = n * Qn + (1 + 2 + ... + (n - 1)) * 2
Substituíndo a soma da PA: (1 + 2 + ... + (n - 1)) = (1 + (n - 1)) * (n - 1) / 2
Output = n * Qn + (1 + (n - 1)) * (n - 1) / 2 * 2
Output = n * Qn + n * (n - 1)
Output = n * Qn + (n2 - n)
Output = n * (n * (n - 1) + 1) + n2 - n
Output = n * (n2 - n + 1) + n2 - n
Output = n3 - n2 + n + n2 - n
Output = n3

Conferindo os resultados:

Output(1) = 13 = 1
Output(2) = 23 = 8
Output(3) = 33 = 27

Logo, a solução do problema é:

def row_sum_odd_numbers(n):
    return n**3

A complexidade espacial desse algoritmo é O(1), pois a quantidade de variáveis é constante. A complexidade temporal desse algoritmo é O(1), pois a multiplicação é uma operações que é feita em tempo constante.

Related Posts

Pesquisar