Beautiful Arrangement

Given an integer n, count the number of beautiful arrangements you can construct using integers 1 to n. A beautiful arrangement is one where for every i, either perm[i] is divisible by i or i is divisible by perm[i].

Example 1

Input: n = 2 → Output: 2

Example 2

Input: n = 1 → Output: 1

Solution Approach

Use backtracking: at each position pos (1-indexed), try placing each unused number. A number k is valid at position pos if k % pos == 0 or pos % k == 0. Use a visited array to track used numbers.

Maintain a boolean visited[] of size n+1.
At each position pos from 1 to n, try all numbers 1..n that are not visited.
Check divisibility condition; if valid, mark visited and recurse to pos+1.
When pos > n, increment count. Backtrack by unmarking visited.

Java

class Solution {
    int count = 0;

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

    private void backtrack(int n, int pos, boolean[] visited) {
        if (pos > n) {
            count++;
            return;
        }
        for (int k = 1; k <= n; k++) {
            if (!visited[k] && (k % pos == 0 || pos % k == 0)) {
                visited[k] = true;
                backtrack(n, pos + 1, visited);
                visited[k] = false;
            }
        }
    }
}

Time Complexity: O(k) where k is number of valid arrangements
Space Complexity: O(N). Visited array + stack