Seating by Divisibility

Medium

A table has n seats numbered 1 to n, and n guests numbered 1 to n arrive. Each guest must get a seat of their own. A seating is good if, for every seat, the guest's number is divisible by the seat's number or the seat's number is divisible by the guest's number. Return how many good seatings exist.

Example 1

n=3 → 3

The valid seatings are [1, 2, 3], [2, 1, 3] and [3, 2, 1]. In [3, 2, 1], for instance, guest 3 is in seat 1 (3 is divisible by 1), guest 2 is in seat 2, and guest 1 is in seat 3 (3 is divisible by 1).

Example 2

n=1 → 1

One guest and one seat give one seating.

Example 3

n=6 → 36

Constraints

1 ≤ n ≤ 15

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Dynamic Programming Backtracking Bitmask

Similar problems

Square Frame From Sticks Medium Cheapest Basket with Bundles Medium Groups With Equal Sums Medium Least Total Walk to Scooters Medium Trainees and Coaches Medium

Input

n=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 18 tests on the server, hidden ones included.