---

1. Problem Summary

You are given an integer n, and you must count how many permutations of numbers 1 through n satisfy the following condition:

For every position i (1-based index):

perm[i] % i == 0   OR   i % perm[i] == 0

These permutations are called Beautiful Arrangements.

Your task is to return the total number of such valid permutations.

Example interpretation:
If n = 2, the valid permutations are:

[1,2]   because 1 % 1 == 0  and  2 % 2 == 0
[2,1]   because 2 % 1 == 0  and  1 % 2 == 1 (but position 2 satisfies i % perm[i] == 0)

So the answer is 2.

---

2. Key Insights

This is a constrained permutation counting problem

Rather than generating all permutations, we only explore valid branches.

Backtracking is ideal

At each position i, only numbers that obey the divisibility rule can be placed.

We must track which numbers are already used

A boolean array or bitmask efficiently marks used numbers.

Ordering matters

Different sequences of the same numbers count as different arrangements.

Search space reduces dramatically due to pruning

Divisibility constraints eliminate most candidates early.

---

3. Approach

Backtracking with pruning

Steps:

1. Maintain a visited array (size n+1) to mark used numbers.
2. Define recursive function dfs(position):
   • If position > n → we found a full valid arrangement → increment count
   • For each number num from 1 to n:
     • If num not used AND divisibility rule holds: num % position == 0 OR position % num == 0
       • mark used
       • recurse to next position
       • unmark used (backtrack)
3. Return total count.

This explores only valid permutations and avoids brute force enumeration.

---

4. Time and Space Complexity

Time Complexity

Worst-case upper bound:

O(n!)

But due to pruning, practical performance is much faster.
For constraints n ≤ 15, backtracking passes comfortably.

Space Complexity

O(n)

For recursion stack + visited array.

---

5. Java Solution

class Solution {

    private int count = 0;

    public int countArrangement(int n) {
        boolean[] used = new boolean[n + 1];
        backtrack(1, n, used);
        return count;
    }

    private void backtrack(int position, int n, boolean[] used) {
        if (position > n) {
            count++;
            return;
        }

        for (int num = 1; num <= n; num++) {
            if (!used[num] && (num % position == 0 || position % num == 0)) {
                used[num] = true;
                backtrack(position + 1, n, used);
                used[num] = false;
            }
        }
    }
}

---

6. Dry Run Examples

Example 1

Input:

n = 1

Only permutation:
[1]

Check:
1 % 1 == 0 → valid

Output:

1

---

Example 2

Input:

n = 2

Possible valid permutations:

[1,2]

• position 1: 1 % 1 == 0
• position 2: 2 % 2 == 0
  Valid

[2,1]

• position 1: 2 % 1 == 0
• position 2: 1 % 2 == 1 but 2 % 1 == 0 (using i % perm[i] condition)
  Valid

Output:

2

---

Example 3

Input:

n = 3

Valid permutations:

1. [1,2,3]
2. [1,3,2]
3. [2,1,3]
4. [3,2,1]

Total:

4

---

Example 4

Input:

n = 4

Valid arrangements count = 8 (not listing all here due to length)

Output:

8

---

Example 5

Input:

n = 5

Output:

10

---

7. Why This Solution Works

• Divisibility rule filters choices early
• Backtracking ensures exploring only feasible permutations
• No wasted computation on invalid branches
• Uses minimal memory
• Works efficiently for maximum constraints

---

8. Common Mistakes

1. Generating full permutations first, then checking validity (too slow)
2. Forgetting that the check is: num % position == 0 OR position % num == 0
3. Incorrect indexing (positions are 1-based)
4. Reusing numbers without marking visited
5. Returning too early before full arrangement completed