# Beautiful Arrangement
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/beautiful-arrangement)
Canonical: https://scaleengineer.com/dsa/problems/beautiful-arrangement
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [Salesforce](https://scaleengineer.com/companies/salesforce), [HashedIn](https://scaleengineer.com/companies/hashedin), [UBS](https://scaleengineer.com/companies/ubs), [MathWorks](https://scaleengineer.com/companies/mathworks)
---
## Problem
Suppose you have `n` integers labeled `1` through `n`. A permutation of those `n` integers `perm` (**1-indexed**) is considered a **beautiful arrangement** if for every `i` (`1 <= i <= n`), **either** of the following is true:

* `perm[i]` is divisible by `i`.
* `i` is divisible by `perm[i]`.

Given an integer `n`, return _the **number** of the **beautiful arrangements** that you can construct_.

**Example 1:**

**Input:** n = 2
**Output:** 2
**Explanation:** 
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

**Constraints:**

* `1 <= n <= 15`

# Approaches
## Brute Force by Generating All Permutations
The most straightforward way to solve this problem is to generate every possible arrangement of numbers from 1 to `n` and then check if each arrangement is "beautiful". We can maintain a counter that gets incremented for every beautiful arrangement found.
**Time:** O(n! * n). There are `n!` possible permutations. For each permutation, we iterate through all `n` elements to check if it's a beautiful arrangement. · **Space:** O(n). The recursion depth can go up to `n`.
**Pros:** Conceptually simple and easy to implement.
**Cons:** Extremely inefficient. The factorial growth makes it infeasible for `n` larger than 10 or 11.
### Explanation
We can implement this using a recursive function that generates all permutations of the numbers.
```java
class Solution {
    int count = 0;
    public int countArrangement(int n) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        permute(nums, 0);
        return count;
    }

    private void permute(int[] nums, int start) {
        if (start == nums.length) {
            if (isBeautiful(nums)) {
                count++;
            }
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1);
            swap(nums, start, i); // backtrack
        }
    }

    private boolean isBeautiful(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // Problem is 1-indexed, so we check nums[i] against position i+1
            if (nums[i] % (i + 1) != 0 && (i + 1) % nums[i] != 0) {
                return false;
            }
        }
        return true;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
- Create an array `nums` containing numbers from 1 to `n`.
- Define a recursive function, say `permute(nums, start)`, which generates all permutations of the subarray starting at `start`.
- The base case for the recursion is when `start` reaches the end of the array. This signifies that a full permutation has been formed.
- In the base case, we call a helper function `isBeautiful(nums)` to check if the generated permutation satisfies the condition for all indices `i` from 1 to `n`.
- If the permutation is beautiful, we increment a global counter.
- The recursive step involves iterating from the `start` index to the end, swapping the element at `start` with the current element, making a recursive call for the next position (`start + 1`), and then swapping back to backtrack and explore other possibilities.

## Backtracking with Pruning
The brute-force approach is inefficient because it generates complete permutations even if they violate the beautiful arrangement condition early on. We can optimize this by building the permutation position by position and checking the condition at each step. If a number placed at a certain position violates the condition, we can prune this entire branch of the search tree and backtrack, avoiding the generation of many invalid permutations.
**Time:** The complexity is difficult to express with a simple formula, but it's roughly proportional to the number of valid partial and full permutations. It's much faster than O(n! * n) and is efficient enough to pass for `n <= 15`. · **Space:** O(n). We use a `visited` array of size `n+1` and the recursion depth is `n`.
**Pros:** Significantly more efficient than brute force due to pruning.; Solves the problem within the given constraints.
**Cons:** Still exponential in nature.; Can be slower than a dynamic programming solution for this specific problem structure.
### Explanation
We use a recursive helper function that tries to place a valid number at each position, one by one. We use a `visited` array to keep track of the numbers that have already been placed in the permutation.
```java
class Solution {
    int count = 0;
    public int countArrangement(int n) {
        boolean[] visited = new boolean[n + 1];
        calculate(n, 1, visited);
        return count;
    }

    private void calculate(int n, int pos, boolean[] visited) {
        if (pos > n) {
            count++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && (i % pos == 0 || pos % i == 0)) {
                visited[i] = true;
                calculate(n, pos + 1, visited);
                visited[i] = false; // backtrack
            }
        }
    }
}
```
### Algorithm
- Define a recursive function `calculate(n, pos, visited)`. `pos` is the current 1-indexed position we are trying to fill.
- The base case is when `pos` becomes greater than `n`, which means we have successfully placed numbers in all `n` positions. We've found one beautiful arrangement, so we increment our count.
- In the recursive step, we iterate through all numbers `i` from 1 to `n`.
- For each number `i`, we check two conditions:
    1. Has `i` been used already? (`!visited[i]`)
    2. Does `i` satisfy the beautiful condition at position `pos`? (`i % pos == 0 || pos % i == 0`)
- If both conditions are met, we mark `i` as visited, make a recursive call for the next position (`pos + 1`), and then unmark `i` as visited to backtrack.

## Dynamic Programming with Bitmasking
Given the small constraint on `n` (`n <= 15`), we can suspect a solution with a time complexity related to `2^n`. This leads to the idea of using dynamic programming with a bitmask. The bitmask can efficiently represent the set of numbers that have been used in the permutation so far.
**Time:** O(n * 2^n). We have a nested loop. The outer loop runs `2^n` times (for each mask), and the inner loop runs `n` times (for each number). · **Space:** O(2^n). We need a DP array of size `2^n` to store the results for all possible masks.
**Pros:** Most efficient time complexity for the given constraints.; Systematic and avoids recursion overhead.
**Cons:** Higher space complexity compared to backtracking.; The concept of bitmask DP can be less intuitive than a direct recursive approach.
### Explanation
We define a DP state `dp[mask]` as the number of beautiful arrangements using a specific subset of numbers from `{1, ..., n}`. The `mask` is an integer where the `i`-th bit is set if the number `i+1` is in the subset. The size of the arrangement is simply the number of set bits in the mask.
```java
class Solution {
    public int countArrangement(int n) {
        int[] dp = new int[1 << n];
        dp[0] = 1;

        for (int mask = 1; mask < (1 << n); mask++) {
            int k = Integer.bitCount(mask);

            for (int j = 0; j < n; j++) {
                // Check if (j+1)-th number is in the mask
                if ((mask & (1 << j)) != 0) {
                    int num = j + 1;
                    // Check if 'num' can be placed at position 'k'
                    if (num % k == 0 || k % num == 0) {
                        // Add ways from the previous state (mask without num)
                        dp[mask] += dp[mask ^ (1 << j)];
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}
```
### Algorithm
- Let `dp[mask]` be the number of ways to place the first `k` numbers into the first `k` positions, where `k` is the number of set bits in `mask` and the numbers used are those corresponding to the set bits.
- Initialize a `dp` array of size `2^n` with all zeros, and set `dp[0] = 1` (representing one way to form an empty arrangement).
- Iterate through each `mask` from 1 to `(1 << n) - 1`.
- For each `mask`, determine the number of elements in the set, `k = Integer.bitCount(mask)`. This `k` also represents the position we are currently trying to fill.
- Iterate through each number `j` from 1 to `n`.
- If number `j` is part of the current set (i.e., the `(j-1)`-th bit is set in `mask`), we check if it can be placed at position `k`.
- The condition is `j % k == 0` or `k % j == 0`.
- If it's a valid placement, it means we can extend the beautiful arrangements of size `k-1` (formed by the numbers in `mask` excluding `j`) by placing `j` at position `k`. The number of such arrangements is `dp[mask ^ (1 << (j-1))]`.
- We add this to our current state: `dp[mask] += dp[mask ^ (1 << (j-1))]`.
- After filling the DP table, the final answer is `dp[(1 << n) - 1]`, which stores the count for arrangements using all `n` numbers in all `n` positions.

# Solutions
### Java

```java
class Solution {
public
  int countArrangement(int N) {
    int maxn = 1 << N;
    int[] f = new int[maxn];
    f[0] = 1;
    for (int i = 0; i < maxn; ++i) {
      int s = 1;
      for (int j = 0; j < N; ++j) {
        s += (i >> j) & 1;
      }
      for (int j = 1; j <= N; ++j) {
        if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) {
          f[i | (1 << (j - 1))] += f[i];
        }
      }
    }
    return f[maxn - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int n;
  int ans;
  vector<bool> vis;
  unordered_map<int, vector<int>> match;
  int countArrangement(int n) {
    this->n = n;
    this->ans = 0;
    vis.resize(n + 1);
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        if (i % j == 0 || j % i == 0)
          match[i].push_back(j);
    dfs(1);
    return ans;
  }
  void dfs(int i) {
    if (i == n + 1) {
      ++ans;
      return;
    }
    for (int j : match[i]) {
      if (!vis[j]) {
        vis[j] = true;
        dfs(i + 1);
        vis[j] = false;
      }
    }
  }
};

```

### Python

```python
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

```