Beautiful Arrangement | Problems

Consider the integers from 1 to n. A beautiful arrangement is a permutation perm of these integers such that, for every position i from 1 to n, either perm[i] is divisible by i or i is divisible by perm[i]. Given n, count how many such beautiful arrangements exist.

Input Format

Implement countArrangement(n). Inputs below show JavaScript function arguments; there is no stdin parsing.

Output Format

Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input

n = 2

Output

Example 2

Input

n = 1

Output

Constraints

1 <= n <= 15

Test Cases (2)

Case 1

Args: [2] Expected: 2

Case 2

Args: [1] Expected: 1

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).

javascript

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(n × n!) as a loose upper bound, including candidate checks at partial arrangements Space: O(n) for recursion stack and visited array

Saved in this browser only. Private to you.