Divisible Seat Assignments
MediumBacktracking
Problem
Guests numbered 1 to n sit in seats numbered 1 to n, one guest per seat. An assignment is harmonious if, for every seat i, the guest g sitting there satisfies g % i == 0 or i % g == 0.
Return the number of harmonious assignments.
Example 1
- Input:
- n = 2
- Output:
- 2
[1, 2]: 1 % 1 = 0 and 2 % 2 = 0. [2, 1]: 2 % 1 = 0 and 2 % 1 = 0 (seat 2, guest 1). Both work.
Example 2
- Input:
- n = 1
- Output:
- 1
Constraints
- 1 ≤ n ≤ 15
Hint
Show the first hint
This is a permutation search with a condition between a guest and the seat they take.
Walkthrough
How to approach it
01Clarify before coding
- Is the condition per seat only? Yes, there is no condition between neighbours.
- Does 1 divide everything? Yes, so guest 1 fits any seat and seat 1 fits any guest.
- Range of n? Up to 15: 15! ≈ 1.3 · 10^12 permutations, so pruning is essential.
02Brute force
Generate all n! permutations and test each seat.
Cost: O(n · n!): already 3.6 million permutations at n = 10 and over a trillion at n = 15.
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.