Beautiful arrangement

Array Dynamic Programming Backtracking Bit Manipulation Bitmask

64.7% acceptance

Feb 19, 2026

3397

390

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_arrangement(n: i32) -> i32 {
    let n = n as usize;
    let mut visited = vec![false; n + 1];
    let mut count = 0i32;
    fn backtrack(pos: usize, n: usize, visited: &mut Vec<bool>, count: &mut i32) {
      if pos > n { *count += 1; return; }
      for i in 1..=n {
        if !visited[i] && (i % pos == 0 || pos % i == 0) {
          visited[i] = true;
          backtrack(pos + 1, n, visited, count);
          visited[i] = false;
        }
      }
    }
    backtrack(1, n, &mut visited, &mut count);
    count
  }
}