Solution Explanation for Beautiful Arrangement

This problem asks us to find the number of beautiful arrangements of integers from 1 to n. A beautiful arrangement is a permutation where for each index i, either the element at that index is divisible by i, or i is divisible by the element at that index.

The most efficient way to solve this problem is using backtracking (or Depth-First Search - DFS). We can also pre-compute possible matches to speed up the process slightly.

Approach:

1. Pre-compute Matches: For each number i from 1 to n, we create a list of numbers j (from 1 to n) such that i is divisible by j or j is divisible by i. This optimization reduces redundant computations during the backtracking process.

2. Backtracking (DFS): We use a recursive function dfs(index) where index represents the current position in the permutation we are constructing.

   • Base Case: If index is n + 1, it means we have built a complete permutation. We increment the count of beautiful arrangements (ans).
   • Recursive Step: For each number j in the list of matches for index, if j has not been used (checked via vis array), we mark j as used, recursively call dfs(index + 1), and then unmark j to explore other possibilities.

3. Return Count: Finally, we return the total count of beautiful arrangements (ans).

Time Complexity Analysis:

• Pre-computation of matches takes O(n^2) time.
• The backtracking algorithm explores a tree where each node represents a position in the permutation and the branches are the possible numbers that can be placed at that position. In the worst case, the tree could have a depth of n and a branching factor of n in some nodes (although this is unlikely in practice). Therefore, the time complexity is approximately O(n!). However, the actual runtime is significantly less due to the pruning done by the vis array, which eliminates many branches early on.

Space Complexity Analysis:

• We use an array vis of size n+1 to track used numbers, requiring O(n) space.
• The match array (or hash map/dictionary) also requires O(n^2) space in the worst case, though in practice the space used will be much less.
• The recursive call stack in the DFS can reach a depth of n, requiring O(n) space in the worst case.

Therefore, the overall space complexity is dominated by the pre-computation, which is O(n^2).

Code (Python):

from collections import defaultdict
 
class Solution:
    def countArrangement(self, n: int) -> int:
        ans = 0
        vis = [False] * (n + 1)
        match = defaultdict(list)
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if j % i == 0 or i % j == 0:
                    match[i].append(j)
 
        def dfs(i):
            nonlocal ans, n
            if i == n + 1:
                ans += 1
                return
            for j in match[i]:
                if not vis[j]:
                    vis[j] = True
                    dfs(i + 1)
                    vis[j] = False
 
        dfs(1)
        return ans

The code in other languages (Java, C++, Go, TypeScript, Rust) follows a similar structure and logic, only differing in syntax and data structures. They all share the same time and space complexity characteristics.