Square Chain Orderings
HardBacktracking
Problem
Call an ordering of the numbers in nums a square chain if every two neighbours add up to a perfect square (0, 1, 4, 9, 16, ...).
Return how many distinct square chains use every number of nums exactly once. Orderings that differ only by swapping equal values count once.
Example 1
- Input:
- nums = [1, 17, 8]
- Output:
- 2
[1, 8, 17] (1 + 8 = 9, 8 + 17 = 25) and its reverse [17, 8, 1].
Example 2
- Input:
- nums = [2, 2, 2]
- Output:
- 1
Only one distinct ordering exists, and 2 + 2 = 4 is a square.
Constraints
- 1 ≤ nums.length ≤ 12
- 0 ≤ nums[i] ≤ 10^9
Hint
Show the first hint
This is 'distinct permutations' with an extra condition between neighbours. Check it while placing, not at the end.
Walkthrough
How to approach it
01Clarify before coding
- Does 0 count as a perfect square? Yes, so 0 + 0 is a valid neighbour pair.
- Do equal values create different chains? No, chains are compared by values.
- Is a single number a chain? Yes, it has no neighbours to violate the rule: answer 1.
02Brute force
Generate all n! orderings, deduplicate them and test every neighbour pair.
Cost: O(n · n!): for n = 12 that is about 479 million orderings times 12 checks, far too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.