Todos os desafios
Médio 0 resolvidos 0% de aceitação

Pares de números pentagonais

Conte os pares de números pentagonais cuja soma também é pentagonal.

O que você vai aprender

  • Gerar números pentagonais
  • Testar a pertinência com uma fórmula
  • Contar pares com um laço duplo

Problema

Ver original (inglês)

Os números pentagonais são P(k) = k(3k − 1) / 2: 1, 5, 12, 22, 35, 51, 70, ... Alguns pares somam outro número pentagonal, como P(4) + P(7) = 22 + 70 = 92 = P(8). Conte os pares j < k ≤ n para os quais P(j) + P(k) é pentagonal. Um teste rápido ajuda: x é pentagonal exatamente quando 24x + 1 é um quadrado perfeito s² com s % 6 = 5.

Implemente pentagonal_pair(n).

Entrada

n: o maior índice k a usar.

Saída

Retorne a quantidade de pares (j, k) com 1 ≤ j < k ≤ n e P(j) + P(k) pentagonal.

Restrições

1 ≤ n ≤ 1000

Exemplos

Exemplo 1
Entrada:
n = 7

Saída esperada:
expected = 1
Entrada:
long long n = 7;

Saída esperada:
long long expected = 1;
Entrada:
long n = 7;

Saída esperada:
long expected = 1;

Explicação

Dos 21 pares até k = 7, só P(4) + P(7) = 92 = P(8) é pentagonal, então a resposta é 1.

Exemplo 2
Entrada:
n = 1

Saída esperada:
expected = 0
Entrada:
long long n = 1;

Saída esperada:
long long expected = 0;
Entrada:
long n = 1;

Saída esperada:
long expected = 0;

Explicação

Não existe par com j < k ≤ 1, então a resposta é 0.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

P(k) = k(3k − 1) / 2.

Dica 2

Verifique se 24x + 1 é um quadrado perfeito usando a raiz quadrada inteira e depois confira a raiz módulo 6.

Dica 3

Só contam os pares com j < k.

Complexidade esperada

tempo O(n²), espaço extra O(n)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.