Problem

Given an integer n, return the number ofpermutations 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]

Examples

Example 1:

1
2
3

Input: n = 1
Output: 1
Explanation: The array [1] has only 1 permutation which is self-divisible.

Example 2:

1
2
3
4
5

Input: n = 2
Output: 1
Explanation: The array [1,2] has 2 permutations and only one of them is self-divisible:
nums = [1,2]: This is not self-divisible since gcd(nums[2], 2) != 1.
nums = [2,1]: This is self-divisible since gcd(nums[1], 1) == 1 and gcd(nums[2], 2) == 1.

Example 3:

1
2
3
4

Input: n = 3
Output: 3
Explanation: The array [1,2,3] has 3 self-divisble permutations: [1,3,2], [3,1,2], [2,3,1].
It can be shown that the other 3 permutations are not self-divisible. Hence the answer is 3.

Constraints:

  • 1 <= n <= 12

Solution

Method 1 – Backtracking with Bitmask

Intuition

We need to count all permutations of [1..n] such that for every position i (1-indexed), gcd(a[i], i) == 1. Since n is small (≤12), we can use backtracking with a bitmask to efficiently try all possible assignments.

Approach

  1. Use a recursive function with parameters: current position i (1-indexed) and a bitmask of used numbers.
  2. For each unused number x in [1..n], if gcd(x, i) == 1, try placing x at position i and recurse.
  3. If all positions are filled, increment the answer.
  4. Use memoization to speed up repeated states (optional for n ≤ 12).
  5. Return the total count.

Code

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

#include <numeric>
class Solution {
public:
    int countSelfDivisiblePermutations(int n) {
        int ans = 0;
        function<void(int,int)> dfs = [&](int i, int mask) {
            if (i > n) { ++ans; return; }
            for (int x = 1; x <= n; ++x) {
                if (!(mask & (1<<(x-1))) && gcd(x,i)==1) {
                    dfs(i+1, mask|(1<<(x-1)));
                }
            }
        };
        dfs(1, 0);
        return ans;
    }
    int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func countSelfDivisiblePermutations(n int) int {
    var ans int
    var gcd func(a, b int) int
    gcd = func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    var dfs func(i, mask int)
    dfs = func(i, mask int) {
        if i > n {
            ans++
            return
        }
        for x := 1; x <= n; x++ {
            if mask&(1<<(x-1)) == 0 && gcd(x,i) == 1 {
                dfs(i+1, mask|(1<<(x-1)))
            }
        }
    }
    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 {
    public int countSelfDivisiblePermutations(int n) {
        return dfs(n, 1, 0);
    }
    int dfs(int n, int i, int mask) {
        if (i > n) return 1;
        int ans = 0;
        for (int x = 1; x <= n; ++x) {
            if ((mask & (1<<(x-1))) == 0 && gcd(x,i) == 1) {
                ans += dfs(n, i+1, mask|(1<<(x-1)));
            }
        }
        return ans;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a%b);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun countSelfDivisiblePermutations(n: Int): Int {
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        var ans = 0
        fun dfs(i: Int, mask: Int) {
            if (i > n) { ans++; return }
            for (x in 1..n) {
                if ((mask and (1 shl (x-1))) == 0 && gcd(x,i) == 1) {
                    dfs(i+1, mask or (1 shl (x-1)))
                }
            }
        }
        dfs(1, 0)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from math import gcd
class Solution:
    def countSelfDivisiblePermutations(self, n: int) -> int:
        ans = 0
        def dfs(i: int, mask: int):
            nonlocal ans
            if i > n:
                ans += 1
                return
            for x in range(1, n+1):
                if not (mask & (1<<(x-1))) and gcd(x,i) == 1:
                    dfs(i+1, mask|(1<<(x-1)))
        dfs(1, 0)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn count_self_divisible_permutations(n: i32) -> i32 {
        fn gcd(mut a: i32, mut b: i32) -> i32 {
            while b != 0 {
                let t = b;
                b = a % b;
                a = t;
            }
            a
        }
        fn dfs(n: i32, i: i32, mask: i32) -> i32 {
            if i > n { return 1; }
            let mut ans = 0;
            for x in 1..=n {
                if (mask & (1<<(x-1))) == 0 && gcd(x,i) == 1 {
                    ans += dfs(n, i+1, mask|(1<<(x-1)));
                }
            }
            ans
        }
        dfs(n, 1, 0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    countSelfDivisiblePermutations(n: number): number {
        function gcd(a: number, b: number): number {
            while (b !== 0) {
                [a, b] = [b, a % b];
            }
            return a;
        }
        let ans = 0;
        function dfs(i: number, mask: number) {
            if (i > n) { ans++; return; }
            for (let x = 1; x <= n; ++x) {
                if ((mask & (1<<(x-1))) === 0 && gcd(x,i) === 1) {
                    dfs(i+1, mask|(1<<(x-1)));
                }
            }
        }
        dfs(1, 0);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n! * n), where n is the input. We try all permutations, and for each, check up to n positions.
  • 🧺 Space complexity: O(n), for recursion stack and bitmask.