611. Graceful Orderings
A dance teacher has n dancers wearing the numbers 1 to n and n spots on the floor numbered 1 to n. A line-up assigns each dancer to a different spot. A line-up is graceful if, for every spot, the dancer's number divides the spot number, or the spot number divides the dancer's number.
Return the number of graceful line-ups. A solution that checks all n! line-ups will be too slow for the largest n; build the line-up spot by spot and give up on a partial line-up as soon as a spot cannot be filled.
Example 1
- Input:
- n = 3
- Output:
- 3
- Explanation:
Three line-ups work: dancers
[1, 2, 3],[2, 1, 3]and[3, 2, 1]in spots 1, 2, 3.
Example 2
- Input:
- n = 4
- Output:
- 8
- Explanation:
Eight graceful line-ups exist for four dancers.
Example 3
- Input:
- n = 5
- Output:
- 10
- Explanation:
Ten graceful line-ups exist for five dancers.
Constraints
- 1 ≤
n≤ 12
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(k) where k is the number of valid prefixes
- Space
- O(n)