Domain 2MediumCORE

Beautiful Arrangement

We are asked to find the total number of permutations perm of length n (containing integers from 1 to n) that satisfy a specific divisibility condition at every index. Specifically, for each position i (where indices range from 1 to n), either the value placed there (perm[i]) must be divisible by the index i, or vice versa (i % perm[i] == 0).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Backtracking#Depth-first Search

526. Beautiful Arrangement

Model: qwen3.5:9b
Topics: Backtracking,Depth-first Search
FAANG asked: 0
Acceptance rate: 62.0%


Problem Breakdown

We are asked to find the total number of permutations perm of length n (containing integers from 1 to n) that satisfy a specific divisibility condition at every index. Specifically, for each position i (where indices range from 1 to n), either the value placed there (perm[i]) must be divisible by the index i, or vice versa (i % perm[i] == 0).

Inputs:

  • Integer n: The size of the permutation and the set of integers used. Range: [1,15][1, 15].

Outputs:

  • An integer representing the count of valid “beautiful arrangements”.

Constraints & Edge Cases:

  • Permutation Property: Every number from 1 to n must appear exactly once in the permutation. This is a critical constraint; we cannot reuse numbers or skip any within a single arrangement attempt.
  • Indexing Mismatch: The problem uses 1-based indexing for logic (ii), but Python lists are 0-indexed. We must adjust our loop variables (e.g., index + 1) to match the mathematical definition of divisibility conditions.
  • Complexity Limits: With n=15n=15, a naive brute-force generation of all permutations is computationally infeasible (O(n!)O(n!)). However, since we only count valid ones and prune invalid branches early during construction, backtracking remains viable within time limits for this specific constraint set.

Intuition

If I were to solve this naively, I would generate every possible permutation using itertools.permutations or a recursive generator and check the condition at each step. However, 15!15! is roughly 1.3 trillion permutations; iterating through all of them will definitely exceed time limits (TLE).

To optimize, we need to build the solution incrementally while validating constraints as soon as possible. This suggests Backtracking. The key insight here is that at any position i, not every number from 11 to nn can be placed there—only those satisfying the divisibility rule. Furthermore, once a number is used for one position in an arrangement attempt, it cannot be reused later (permutation constraint).

By maintaining state on which numbers have been “used” so far, we avoid generating invalid partial permutations that violate these rules immediately. If no valid unused number exists for current index i, the recursion stops there and backtracks to try a different path at previous indices. This pruning drastically reduces the search space compared to checking full n!n! paths.

Approach

We will implement a Depth-First Search (DFS) with backtracking function, say _dfs(index, used_numbers).

  1. State: We track index representing which position in the permutation we are currently filling (00 to n−1n-1, corresponding to logical positions 11 to nn).
  2. Tracking Used Numbers: A boolean array or list of size n+1 (to accommodate values 1..n1..n) will track if a number has been placed in the current permutation branch. This allows O(1)O(1) lookup and marking/unmarking.
  3. Recursive Step: At each position, iterate through all candidate numbers from 11 to n.
    • Check if the candidate is unused (used[num] is false).
    • Check divisibility condition: (num % (index + 1) == 0) or ((index + 1) % num == 0).
  4. Base Case: If we successfully fill all positions up to index n−1n-1 (meaning logical position nn), return 1, indicating one valid arrangement found.
  5. Backtracking Logic: Mark the number as used, recurse for index + 1, then unmark it before returning so that other branches can use this number at different positions.

Complexity Analysis

  • Time Complexity: In the worst case (without pruning), generating permutations is O(n!)O(n!). However, due to the divisibility constraints and the requirement to use each number exactly once, many branches are pruned early in the recursion tree. For n=15n=15, this backtracking approach runs well within typical time limits for LeetCode problems of this type (typically under 20ms-100ms depending on language).
  • Space Complexity: The space complexity is dominated by the recursion stack depth, which goes up to n, and the storage for tracking used numbers. Thus, it is O(n)O(n).

Solution

class Solution:
    def countBeautifulArrangement(self, n: int) -> int:
        # Track usage of each number 1..n. Index i corresponds to value i+1 in list logic 
        # but we'll use a size n+1 array for direct mapping if needed or adjust indices.
        # Using boolean list where index represents the number itself (0 unused).
        used = [False] * (n + 1)
        
        def backtrack(index):
            # Base case: If we have filled positions up to n-1, return 1 valid arrangement found
            if index == n:
                return 1
            
            count = 0
            for num in range(1, n + 1):
                # Check divisibility condition with current logical position (index + 1)
                # Condition: perm[i] % i == 0 OR i % perm[i] == 0
                if not used[num]:
                    pos = index + 1 
                    
                    if num % pos == 0 or pos % num == 0:
                        used[num] = True
                        count += backtrack(index + 1)
                        used[num] = False # Backtrack
                        
            return count

        return backtrack(0)

Edge Cases Handled

  • n = 1: The loop runs once for num=1, condition holds (1%1==01\%1==0), recurses to base case, returns 1. Correctly handles the smallest input.
  • No valid numbers at a position: If no unused number satisfies divisibility for current index (e.g., specific constraints on nn where only certain permutations work), the loop finishes and count remains unchanged, correctly returning 0 from that branch before backtracking up.
  • Constraint Limits (N≤15N \le 15): The recursion depth is limited to 15 frames, well within Python’s default stack limit (usually ~1000). Integer overflow for the count result is not possible as it fits standard integer types comfortably.