Skip to content

2992. Number of Self-Divisible Permutations πŸ”’

Description

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]

 

Example 1:

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

Example 2:

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:

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

Solutions

We can use a binary number \(mask\) to represent the current permutation state, where the \(i\)-th bit is \(1\) indicates that the number \(i\) has been used, and \(0\) indicates that the number \(i\) has not been used yet.

Then, we design a function \(dfs(mask)\), which represents the number of permutations that can be constructed from the current permutation state \(mask\) and meet the requirements of the problem. The answer is \(dfs(0)\).

We can use the method of memoization search to calculate the value of \(dfs(mask)\).

In the process of calculating \(dfs(mask)\), we use \(i\) to indicate which number is to be added to the permutation. If \(i \gt n\), it means that the permutation has been constructed, and we can return \(1\).

Otherwise, we enumerate the numbers \(j\) that have not been used in the current permutation. If \(i\) and \(j\) meet the requirements of the problem, then we can add \(j\) to the permutation. At this time, the state becomes \(mask \mid 2^j\), where \(|\) represents bitwise OR operation. Since \(j\) has been used, we need to recursively calculate the value of \(dfs(mask \mid 2^j)\) and add it to \(dfs(mask)\).

Finally, we can get the value of \(dfs(0)\), which is the answer.

The time complexity is \(O(n \times 2^n)\), and the space complexity is \(O(2^n)\). Where \(n\) is the length of the permutation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def selfDivisiblePermutationCount(self, n: int) -> int:
        @cache
        def dfs(mask: int) -> int:
            i = mask.bit_count() + 1
            if i > n:
                return 1
            ans = 0
            for j in range(1, n + 1):
                if (mask >> j & 1) == 0 and gcd(i, j) == 1:
                    ans += dfs(mask | 1 << j)
            return ans

        return dfs(0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private int n;
    private Integer[] f;

    public int selfDivisiblePermutationCount(int n) {
        this.n = n;
        f = new Integer[1 << (n + 1)];
        return dfs(0);
    }

    private int dfs(int mask) {
        if (f[mask] != null) {
            return f[mask];
        }
        int i = Integer.bitCount(mask) + 1;
        if (i > n) {
            return 1;
        }
        f[mask] = 0;
        for (int j = 1; j <= n; ++j) {
            if ((mask >> j & 1) == 0 && (i % j == 0 || j % i == 0)) {
                f[mask] += dfs(mask | 1 << j);
            }
        }
        return f[mask];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int selfDivisiblePermutationCount(int n) {
        int f[1 << (n + 1)];
        memset(f, -1, sizeof(f));
        function<int(int)> dfs = [&](int mask) {
            if (f[mask] != -1) {
                return f[mask];
            }
            int i = __builtin_popcount(mask) + 1;
            if (i > n) {
                return 1;
            }
            f[mask] = 0;
            for (int j = 1; j <= n; ++j) {
                if ((mask >> j & 1) == 0 && (i % j == 0 || j % i == 0)) {
                    f[mask] += dfs(mask | 1 << j);
                }
            }
            return f[mask];
        };
        return dfs(0);
    }
};

 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 selfDivisiblePermutationCount(n int) int {
    f := make([]int, 1<<(n+1))
    for i := range f {
        f[i] = -1
    }
    var dfs func(int) int
    dfs = func(mask int) int {
        if f[mask] != -1 {
            return f[mask]
        }
        i := bits.OnesCount(uint(mask)) + 1
        if i > n {
            return 1
        }
        f[mask] = 0
        for j := 1; j <= n; j++ {
            if mask>>j&1 == 0 && (i%j == 0 || j%i == 0) {
                f[mask] += dfs(mask | 1<<j)
            }
        }
        return f[mask]
    }
    return dfs(0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function selfDivisiblePermutationCount(n: number): number {
    const f: number[] = Array(1 << (n + 1)).fill(-1);
    const dfs = (mask: number): number => {
        if (f[mask] !== -1) {
            return f[mask];
        }
        const i = bitCount(mask) + 1;
        if (i > n) {
            return 1;
        }
        f[mask] = 0;
        for (let j = 1; j <= n; ++j) {
            if (((mask >> j) & 1) === 0 && (i % j === 0 || j % i === 0)) {
                f[mask] += dfs(mask | (1 << j));
            }
        }
        return f[mask];
    };
    return dfs(0);
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

Solution 2: State Compression + Dynamic Programming

We can rewrite the memoization search in Solution 1 into the form of dynamic programming, define \(f[mask]\) to represent the number of permutations that the current permutation state is \(mask\) and meet the requirements of the problem. Initially, \(f[0]=1\), and the rest are \(0\).

We enumerate \(mask\) in the range of \([0, 2^n)\), for each \(mask\), we use \(i\) to represent which number is the last one to join the permutation, then we enumerate the last number \(j\) added to the current permutation. If \(i\) and \(j\) meet the requirements of the problem, then the state \(f[mask]\) can be transferred from the state \(f[mask \oplus 2^(j-1)]\), where \(\oplus\) represents bitwise XOR operation. We add all the values of the transferred state \(f[mask \oplus 2^(j-1)]\) to \(f[mask]\), which is the value of \(f[mask]\).

Finally, we can get the value of \(f[2^n - 1]\), which is the answer.

The time complexity is \(O(n \times 2^n)\), and the space complexity is \(O(2^n)\). Where \(n\) is the length of the permutation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def selfDivisiblePermutationCount(self, n: int) -> int:
        f = [0] * (1 << n)
        f[0] = 1
        for mask in range(1 << n):
            i = mask.bit_count()
            for j in range(1, n + 1):
                if (mask >> (j - 1) & 1) == 1 and gcd(i, j) == 1:
                    f[mask] += f[mask ^ (1 << (j - 1))]
        return f[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int selfDivisiblePermutationCount(int n) {
        int[] f = new int[1 << n];
        f[0] = 1;
        for (int mask = 0; mask < 1 << n; ++mask) {
            int i = Integer.bitCount(mask);
            for (int j = 1; j <= n; ++j) {
                if (((mask >> (j - 1)) & 1) == 1 && (i % j == 0 || j % i == 0)) {
                    f[mask] += f[mask ^ (1 << (j - 1))];
                }
            }
        }
        return f[(1 << n) - 1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int selfDivisiblePermutationCount(int n) {
        int f[1 << n];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int mask = 0; mask < 1 << n; ++mask) {
            int i = __builtin_popcount(mask);
            for (int j = 1; j <= n; ++j) {
                if (((mask >> (j - 1)) & 1) == 1 && (i % j == 0 || j % i == 0)) {
                    f[mask] += f[mask ^ (1 << (j - 1))];
                }
            }
        }
        return f[(1 << n) - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func selfDivisiblePermutationCount(n int) int {
    f := make([]int, 1<<n)
    f[0] = 1
    for mask := 0; mask < 1<<n; mask++ {
        i := bits.OnesCount(uint(mask))
        for j := 1; j <= n; j++ {
            if mask>>(j-1)&1 == 1 && (i%j == 0 || j%i == 0) {
                f[mask] += f[mask^(1<<(j-1))]
            }
        }
    }
    return f[(1<<n)-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function selfDivisiblePermutationCount(n: number): number {
    const f: number[] = Array(1 << n).fill(0);
    f[0] = 1;
    for (let mask = 0; mask < 1 << n; ++mask) {
        const i = bitCount(mask);
        for (let j = 1; j <= n; ++j) {
            if ((mask >> (j - 1)) & 1 && (i % j === 0 || j % i === 0)) {
                f[mask] += f[mask ^ (1 << (j - 1))];
            }
        }
    }
    return f.at(-1)!;
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

Comments