Beautiful Arrangement

Solution Walkthrough

Approach: Backtracking, Filling Positions in Reverse (O(k) time, O(n) space)

Walk position pos from n down to 1. At each position try every unused value v in 1..n such that v % pos == 0 OR pos % v == 0. When pos == 0, increment the counter.

Key Insight

The order of position-filling matters for pruning. A position pos near n accepts only values v where pos % v == 0 or v % pos == 0, and for large pos this is a small set (most small values fail the modular check). Fewer candidates near the top of the tree means a narrower upper portion of the search and earlier dead-ends.

For example, at pos = n = 15, only v in {1, 3, 5, 15} (the divisors of 15, plus values for which 15 divides them, but no v <= n other than 15 is a multiple of 15) can be placed. So the root branches to 4 children, not 15.

Algorithm

1. Allocate used[1..n] = false and count = 0.
2. Call backtrack(pos = n).
3. In backtrack(pos):

   • If pos == 0: count += 1; return.
   • For v in 1..n:

     • If used[v], skip.
     • If v % pos != 0 && pos % v != 0, skip (divisibility violation).
     • Mark used[v] = true, recurse with pos - 1, unmark.
4. Return count.

Why It Works

The recursion enumerates assignments of distinct values to positions; the divisibility filter rejects illegal placements at the current position only. Since the constraint is per-index and a placed value only affects the current position, filtering inside the loop is sound. Visiting positions in reverse changes the order of the search but not its membership; the count is identical to a forward search.

Complexity

Branching factor at pos

pos=15  -> {1, 3, 5, 15}                       (4 candidates)
pos=14  -> {1, 2, 7, 14} minus already-used     (<= 4)
pos=2   -> any even unused value or 1            (~n/2)
pos=1   -> all remaining unused values           (~k)

Time    O(branching product, much smaller than n!)
Space   O(n) for used[] + recursion stack

For n = 15, empirical search visits ~25K leaves vs 15! = 1.3T, a 50-million-fold speedup from divisibility pruning.

Pitfalls

1. Filling positions left-to-right. Position 1 accepts every value (since v % 1 == 0 always), so the top-level branching factor is n, not 4. The total work is the same in the worst case but pruning kicks in much later.
2. Re-allocating used[] per recursion. The used array is shared across the whole search; allocate once at the top, mark+unmark on the path. Cloning per call inflates space and time.
3. Forgetting the OR semantics. The condition is v divides pos OR pos divides v, NOT both. Using && gives the wrong count.