Problema
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
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.
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.