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: .
Outputs:
- An integer representing the count of valid “beautiful arrangements”.
Constraints & Edge Cases:
- Permutation Property: Every number from
1tonmust 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 (), 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 , a naive brute-force generation of all permutations is computationally infeasible (). 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, 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 to 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 paths.
Approach
We will implement a Depth-First Search (DFS) with backtracking function, say _dfs(index, used_numbers).
- State: We track
indexrepresenting which position in the permutation we are currently filling ( to , corresponding to logical positions to ). - Tracking Used Numbers: A boolean array or list of size
n+1(to accommodate values ) will track if a number has been placed in the current permutation branch. This allows lookup and marking/unmarking. - Recursive Step: At each position, iterate through all candidate numbers from to
n.- Check if the candidate is unused (
used[num]is false). - Check divisibility condition:
(num % (index + 1) == 0)or((index + 1) % num == 0).
- Check if the candidate is unused (
- Base Case: If we successfully fill all positions up to index (meaning logical position ), return 1, indicating one valid arrangement found.
- 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 . 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 , 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 .
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 (), 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 where only certain permutations work), the loop finishes and
countremains unchanged, correctly returning 0 from that branch before backtracking up. - Constraint Limits (): 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.