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 thenumber of the beautiful arrangements that you can construct.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

1
2

Input: n = 1
Output: 1

Constraints

  • 1 <= n <= 15

Solution

Method 1 – Backtracking with Bitmask

Intuition

The problem asks for the number of permutations where, for each position, the number at that position is divisible by its index or vice versa. Since n is small (≤ 15), we can use backtracking to try all possible arrangements efficiently. Using a bitmask helps us track which numbers have been used so far.

Approach

  1. Use a recursive function to try placing each unused number at the current position.
  2. For each position i (starting from 1), iterate through all numbers from 1 to n.
  3. If a number num is not used and either num % i == 0 or i % num == 0, place it at position i.
  4. Mark num as used (using bitmask), recurse for the next position.
  5. When all positions are filled, increment the answer.
  6. Backtrack by unmarking the number and continue.
  7. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
  int countArrangement(int n) {
    int ans = 0;
    function<void(int, int)> dfs = [&](int pos, int mask) {
      if (pos > n) {
        ans++;
        return;
      }
      for (int num = 1; num <= n; ++num) {
        if (!(mask & (1 << num)) && (num % pos == 0 || pos % num == 0)) {
          dfs(pos + 1, mask | (1 << num));
        }
      }
    };
    dfs(1, 0);
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func countArrangement(n int) int {
  ans := 0
  var dfs func(int, int)
  dfs = func(pos, mask int) {
    if pos > n {
      ans++
      return
    }
    for num := 1; num <= n; num++ {
      if mask&(1<<num) == 0 && (num%pos == 0 || pos%num == 0) {
        dfs(pos+1, mask|(1<<num))
      }
    }
  }
  dfs(1, 0)
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
  int ans = 0;
  public int countArrangement(int n) {
    dfs(n, 1, 0);
    return ans;
  }
  void dfs(int n, int pos, int mask) {
    if (pos > n) {
      ans++;
      return;
    }
    for (int num = 1; num <= n; num++) {
      if ((mask & (1 << num)) == 0 && (num % pos == 0 || pos % num == 0)) {
        dfs(n, pos + 1, mask | (1 << num));
      }
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
  var ans = 0
  fun countArrangement(n: Int): Int {
    fun dfs(pos: Int, mask: Int) {
      if (pos > n) {
        ans++
        return
      }
      for (num in 1..n) {
        if ((mask and (1 shl num)) == 0 && (num % pos == 0 || pos % num == 0)) {
          dfs(pos + 1, mask or (1 shl num))
        }
      }
    }
    dfs(1, 0)
    return ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
  def countArrangement(self, n: int) -> int:
    ans: int = 0
    def dfs(pos: int, mask: int) -> None:
      nonlocal ans
      if pos > n:
        ans += 1
        return
      for num in range(1, n + 1):
        if not (mask & (1 << num)) and (num % pos == 0 or pos % num == 0):
          dfs(pos + 1, mask | (1 << num))
    dfs(1, 0)
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
  pub fn count_arrangement(n: i32) -> i32 {
    fn dfs(n: i32, pos: i32, mask: i32, ans: &mut i32) {
      if pos > n {
        *ans += 1;
        return;
      }
      for num in 1..=n {
        if (mask & (1 << num)) == 0 && (num % pos == 0 || pos % num == 0) {
          dfs(n, pos + 1, mask | (1 << num), ans);
        }
      }
    }
    let mut ans = 0;
    dfs(n, 1, 0, &mut ans);
    ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
  countArrangement(n: number): number {
    let ans = 0;
    function dfs(pos: number, mask: number): void {
      if (pos > n) {
        ans++;
        return;
      }
      for (let num = 1; num <= n; num++) {
        if ((mask & (1 << num)) === 0 && (num % pos === 0 || pos % num === 0)) {
          dfs(pos + 1, mask | (1 << num));
        }
      }
    }
    dfs(1, 0);
    return ans;
  }
}

Complexity

  • ⏰ Time complexity: O(n!) (since we try all permutations, but pruning reduces actual calls)
  • 🧺 Space complexity: O(n) (recursion stack and bitmask)