#526

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Beautiful Arrangement

The Beautiful Arrangement problem asks for the number of valid permutations of n integers satisfying specific divisibility conditions.

array dynamic programming backtracking bit manipulation bitmask

Problem Statement

Given an integer n, you are tasked with constructing permutations of integers 1 through n. A permutation is considered a beautiful arrangement if for each position i (1 ≤ i ≤ n), one of the following is true: either the integer at position i is divisible by i, or i is divisible by the integer at position i.

Your goal is to return the number of valid beautiful arrangements that can be constructed for the given n. The problem can be tackled using dynamic programming and backtracking techniques to efficiently generate and count valid arrangements.

Examples

Example 1

Input: n = 2

Output: 2

The first beautiful arrangement is [1,2]:

perm[1] = 1 is divisible by i = 1
perm[2] = 2 is divisible by i = 2 The second beautiful arrangement is [2,1]:
perm[1] = 2 is divisible by i = 1
i = 2 is divisible by perm[2] = 1

Example 2

Input: n = 1

Output: 1

Example details omitted.

Constraints

1 <= n <= 15

Solution Approach

Backtracking with State Transitions

The problem can be approached by recursively attempting to build the arrangement, checking the divisibility condition at each step. At each position, backtracking allows the exploration of different valid configurations, while dynamic programming is employed to remember previous state results to avoid redundant calculations.

Bitmask Dynamic Programming

This approach utilizes a bitmask to represent which numbers have been used in the arrangement. By iterating over the unused numbers and checking the divisibility constraints, we can efficiently count the valid arrangements through dynamic state transitions.

Pruning with Constraints

Incorporating constraints such as the divisibility checks in each step helps prune invalid paths early, minimizing unnecessary exploration. This makes the backtracking approach more efficient by reducing the search space and improving performance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach but generally involves recursion with memoization or bitmasking, leading to a complexity of O(n!) in the worst case. Space complexity is influenced by the storage of state information and intermediate results, such as the bitmask or dynamic programming tables, making it O(n) or O(n!) depending on the implementation details.

What Interviewers Usually Probe

Understanding of dynamic programming principles and backtracking.
Ability to optimize search space using bitmasking.
Familiarity with state transitions and pruning techniques.

Common Pitfalls or Variants

Common pitfalls

Overlooking the need for pruning, leading to excessive recursion.
Failing to properly handle base cases or conditions during recursion.
Mismanaging state transitions when using dynamic programming or bitmasking.

Follow-up variants

Increasing n beyond 15 to test scalability.
Modifying the divisibility rule for more complex conditions.
Limiting the problem to only odd or even positions.

FAQ

What is the pattern behind the Beautiful Arrangement problem?

The problem primarily revolves around state transition dynamic programming, utilizing backtracking and bitmasking techniques to efficiently find valid permutations.

How can backtracking help with the Beautiful Arrangement problem?

Backtracking allows you to explore possible valid arrangements by trying each number in each position while checking the divisibility conditions. It helps prune invalid paths early, saving time.

What is the time complexity of solving the Beautiful Arrangement problem?

The time complexity generally involves recursion with dynamic programming or bitmasking, leading to O(n!) in the worst case, depending on the implementation approach.

How can I optimize my solution for larger n values?

Optimizing with memoization, dynamic programming, and bitmasking significantly reduces the complexity, enabling the solution to scale for larger n values.

What is a common mistake when implementing the Beautiful Arrangement solution?

A common mistake is failing to manage the divisibility condition properly, leading to invalid permutations or incorrect counts.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def countArrangement(self, n: int) -> int:
        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

        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)

        dfs(1)
        return ans

Solution 2

#### Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def countArrangement(self, n: int) -> int:
        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

        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)

        dfs(1)
        return ans

Continue Practicing

#473 matchsticks to square #638 shopping offers #691 stickers to spell word