Skip to main content
Back to problems
#2992
Medium Algorithms

Number of self divisible permutations

Array Math Dynamic Programming Backtracking Bit Manipulation Number Theory Bitmask
71.8% acceptance
Mar 31, 2026
22
0
Given an integer n, return the number of permutations of the 1-indexed array nums = [1, 2, ..., n], such that it's self-divisible. A 1-indexed array a of length n is self-divisible if for every 1 <= i <= n, gcd(a[i], i) == 1. A permutation of an array is a rearrangement of the elements of that array, for example here are all of the permutations of the array [1, 2, 3]: [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn self_divisible_permutation_count(n: i32) -> i32 {
    fn gcd(a: usize, b: usize) -> usize {
      if b == 0 { a } else { gcd(b, a % b) }
    }
    let n = n as usize;
    let mut dp = vec![0i32; 1 << n];
    dp[0] = 1;
    for mask in 1..(1 << n) {
      let pos = (mask as u32).count_ones() as usize;
      for v in 1..=n {
        if mask & (1 << (v - 1)) != 0 && gcd(v, pos) == 1 {
          dp[mask] += dp[mask ^ (1 << (v - 1))];
        }
      }
    }
    dp[(1 << n) - 1]
  }
}