Beautiful Arrangement | Problems

Suppose you have n integers from 1 to n. We define a beautiful arrangement as an array that is constructed by these n integers such that for every i (1 <= i <= n), either details[i] % i == 0 or i % details[i] == 0. Given an integer n, return the number of the beautiful arrangements that you can construct.

Sample Input

n = 2

Sample Output

Constraints

1 <= n <= 15

Test Cases

Case 1

Args: [2] Expected: 2

Topics

Backtracking Recursion

Use backtracking to place numbers 1 to n into positions 1 to n. At each position, only place a number if it satisfies the divisibility condition (position divides number or number divides position).

function countArrangement(n) {
  let count = 0;
  const visited = new Array(n + 1).fill(false);

  function backtrack(pos) {
    if (pos > n) {
      count++;
      return;
    }
    for (let num = 1; num <= n; num++) {
      if (!visited[num] && (num % pos === 0 || pos % num === 0)) {
        visited[num] = true;
        backtrack(pos + 1);
        visited[num] = false;
      }
    }
  }

  backtrack(1);
  return count;
}

Time: O(k) where k is the number of valid permutations (bounded by n!) Space: O(n) for recursion stack and visited array

Saved in this browser only. Private to you.