Show problems as
Classic problem #526MediumArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask

Beautiful Arrangement

Real-world version: Divisible Crate Placements
Tracked in this browser only
Read Beautiful Arrangement on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A stockroom has size shelves, numbered 1 through size, and size crates, also numbered 1 through size. Exactly one crate goes on each shelf.

A crate is allowed on a shelf only when the two numbers divide one another: the crate number is a multiple of the shelf number, or the shelf number is a multiple of the crate number. Either direction is fine.

Return how many different complete placements satisfy that rule. Two placements differ when some shelf holds a different crate.

Examples

Example 1

Input
size = 3
Output
3

Writing a placement as the crate on shelf 1, shelf 2, shelf 3, the allowed placements are (1, 2, 3), (2, 1, 3) and (3, 2, 1). Shelf 1 accepts any crate, and shelf 3 accepts only crate 1 or crate 3.

Example 2

Input
size = 4
Output
8

Eight complete placements obey the rule, one of them being (2, 4, 3, 1): crate 2 on shelf 1, crate 4 on shelf 2, crate 3 on shelf 3 and crate 1 on shelf 4.

Example 3

Input
size = 5
Output
10

Ten placements obey the rule. Crate 5 can only sit on shelf 1 or shelf 5, and crate 3 can only sit on shelf 1 or shelf 3.

Example 4

Input
size = 6
Output
36

Thirty-six placements obey the rule, for instance (6, 2, 3, 4, 5, 1) and (1, 6, 3, 4, 5, 2).

Constraints

  • 1 <= size <= 15

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_placements(size: int) -> int:
Java
public int countPlacements(int size)

More on the same topics