The O(n) Club: Beautiful Arrangement: Why Backtracking Is Actually Beautiful (Sorry, Not Sorry)

The O(n) Club: Beautiful Arrangement — Why Backtracking Is Actually Beautiful (Sorry, Not Sorry)

⚡ TL;DR

Count permutations of 1 to n where, at each 1-based seat, the number sitting there must divide or be divisible by its seat position. Brute-force is O(n!) — great if you miss hearing your laptop fan. So, we backtrack with style.

// Brute-force (warning: your CPU will hate you)
int count = 0;
for (List<Integer> perm : allPermutations(1..n)) {
    boolean beautiful = true;
    for (int i = 1; i <= n; i++) {
        int num = perm.get(i - 1);
        if (num % i != 0 && i % num != 0) {
            beautiful = false;
            break;
        }
    }
    if (beautiful) count++;
}
// Don't. Just don't.

🧠 How Devs Usually Mess This Up

Some devs treat 1-based positions like an urban legend and go 0-based instead — instant facepalm. Others try generating all n! permutations and filtering for the condition, which, for n=12, will leave you enough time to write your memoir. Some even check only one divisibility direction (perm[i] divides i), missing half the beautiful world. Result: bugs, timeouts, existential dread.

🔍 What’s Actually Going On

This is seating arrangement with rules: guests (numbers) only sit in chairs (positions) where someone divides someone. Don’t waste time inviting every guest to every chair. For each position, precompute who’s allowed, then place them recursively, only using those who aren’t already at the table. Think speed dating, but everyone has to swap seat numbers and compare their divisibility credentials before committing.

• Your guests: numbers 1..n. Your seats: positions 1..n.
• Precompute who’s even eligible for each seat, to speed things up.
• Use backtracking: try a guest, mark them as present, recurse to the next seat. If it fizzles out, backtrack — and keep the existential crisis to a minimum.

🛠️ PseudoCode

• Precompute valid numbers for each seat:

  List<List<Integer>> candidates = new ArrayList<>();
  for (int seat = 1; seat <= n; seat++) {
      List<Integer> options = new ArrayList<>();
      for (int guest = 1; guest <= n; guest++) {
          if (guest % seat == 0 || seat % guest == 0) options.add(guest);
      }
      candidates.add(options);
  }

• Track who’s already sitting with a visited[] array. (Bitmask if you’re feeling spicy.)
• Backtracking magic:

  void dfs(int seat, boolean[] visited) {
      if (seat > n) { count++; return; }
      for (int guest : candidates.get(seat - 1)) {
          if (!visited[guest]) {
              visited[guest] = true;
              dfs(seat + 1, visited);
              visited[guest] = false;
          }
      }
  }

💻 The Code

public class Solution {
    private int count = 0;
    public int countArrangement(int n) {
        List<List<Integer>> candidates = new ArrayList<>();
        for (int pos = 1; pos <= n; pos++) {
            List<Integer> list = new ArrayList<>();
            for (int num = 1; num <= n; num++) {
                if (num % pos == 0 || pos % num == 0) list.add(num);
            }
            candidates.add(list);
        }
        boolean[] visited = new boolean[n + 1]; // 1-based, 0 is unused
        dfs(1, candidates, visited, n);
        return count;
    }
    private void dfs(int pos, List<List<Integer>> candidates, boolean[] visited, int n) {
        if (pos > n) { count++; return; }
        for (int num : candidates.get(pos - 1)) {
            if (!visited[num]) {
                visited[num] = true;
                dfs(pos + 1, candidates, visited, n);
                visited[num] = false;
            }
        }
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• 1-based index (not 0-based!): If you mess this up, you’ll be debugging longer than you’ll be coding.
• Don’t generate every permutation: Seriously, O(n!) hurts more than stubbing your toe on a server rack.
• Edge cases: n=1 returns 1, and for n=15, you’re still fine because of all the pruning.
• Time/space: Recursion tree is big but way smaller than n! due to rules; space is O(n) for visited[] and candidates. Manageable even after three shots of espresso.

🧠 Interviewer Brain-Tattoo

“If brute-force is your first draft, try backtracking before your interviewer backtracks your offer.”