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

Produtos pandigitais

Some os produtos cuja equação a × b = c usa os dígitos de 1 a n exatamente uma vez.

O que você vai aprender

  • Gerar permutações de dígitos
  • Testar todas as divisões em três partes
  • Eliminar resultados repetidos com um conjunto

Problema

Ver original (inglês)

Escreva uma multiplicação a × b = c e observe todos os dígitos de a, b e c juntos. A equação é n-pandigital quando esses dígitos são 1, 2, ..., n, cada um usado exatamente uma vez (sem zeros). Para n = 4, 3 × 4 = 12 se encaixa. Encontre todo produto c que aparece em alguma equação n-pandigital.

Implemente pandigital_products(n).

Entrada

n: o maior dígito a usar.

Saída

Retorne a soma dos produtos c distintos. Um produto obtido por mais de uma equação é somado uma única vez. Se não houver nenhum, retorne 0.

Restrições

1 ≤ n ≤ 9

Exemplos

Exemplo 1
Entrada:
n = 4

Saída esperada:
expected = 12
Entrada:
long long n = 4;

Saída esperada:
long long expected = 12;
Entrada:
long n = 4;

Saída esperada:
long expected = 12;

Explicação

3 × 4 = 12 usa 1, 2, 3, 4 uma vez cada e é a única equação assim, então a resposta é 12.

Exemplo 2
Entrada:
n = 3

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

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

Saída esperada:
long expected = 0;

Explicação

Com os dígitos 1, 2, 3, as únicas divisões possíveis são do tipo 1 × 2 = 3, que é falsa, então a resposta é 0.

Como abordar

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

Dica 1

Toda equação n-pandigital é uma ordenação dos dígitos de 1 a n cortada em três pedaços.

Dica 2

Teste todos os pares de pontos de corte e verifique se os dois primeiros pedaços multiplicados dão o terceiro.

Dica 3

Guarde os produtos em um conjunto para que cada um seja somado uma única vez.

Complexidade esperada

tempo O(n! × n²), espaço extra O(number of products)

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.