All challenges
Medium 0 solved 0% acceptance

Pandigital Products

Add up the products whose equation a × b = c uses the digits 1 to n exactly once.

What you'll learn

  • Generate permutations of digits
  • Try every split into three parts
  • Deduplicate results with a set

Problem

Write a multiplication a × b = c and look at all the digits in a, b and c together. The equation is n-pandigital when those digits are 1, 2, ..., n, each used exactly once (no zeros). For n = 4, 3 × 4 = 12 qualifies. Find every product c that appears in some n-pandigital equation.

Implement pandigital_products(n).

Input

n: The largest digit to use.

Output

Return the sum of the distinct products c. A product reached by more than one equation is added once. If there is none, return 0.

Constraints

1 ≤ n ≤ 9

Examples

Example 1
Input:
n = 4

Expected output:
expected = 12
Input:
long long n = 4;

Expected output:
long long expected = 12;
Input:
long n = 4;

Expected output:
long expected = 12;

Explanation

3 × 4 = 12 uses 1, 2, 3, 4 once each and it is the only such equation, so the answer is 12.

Example 2
Input:
n = 3

Expected output:
expected = 0
Input:
long long n = 3;

Expected output:
long long expected = 0;
Input:
long n = 3;

Expected output:
long expected = 0;

Explanation

With the digits 1, 2, 3 the only splits are like 1 × 2 = 3, which is false, so the answer is 0.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Every n-pandigital equation is an ordering of the digits 1 to n cut into three pieces.

Hint 2

Try every cut point pair and check whether the first two pieces multiply to the third.

Hint 3

Store products in a set so each is added once.

Expected complexity

O(n! × n²) time, O(number of products) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.