How hard is LeetCode 2992. Number of Self-Divisible Permutations?

LeetCode 2992. Number of Self-Divisible Permutations is rated Medium on LeetCode.

What is the time complexity of LeetCode 2992. Number of Self-Divisible Permutations?

The Python solution on this page runs in O(n \times 2^n).

What is the space complexity of LeetCode 2992. Number of Self-Divisible Permutations?

The Python solution on this page uses O(2^n) auxiliary space.

What topics does LeetCode 2992. Number of Self-Divisible Permutations cover?

LeetCode 2992. Number of Self-Divisible Permutations is tagged Bit Manipulation, Array, Math, Dynamic Programming, Backtracking, Bitmask and Number Theory on LeetCode.

Is LeetCode 2992. Number of Self-Divisible Permutations a premium problem?

Yes. LeetCode 2992. Number of Self-Divisible Permutations is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Number of Self-Divisible Permutations — LeetCode 2992 Python Solution

MediumLeetCode PremiumBit ManipulationArrayMathDynamic ProgrammingBacktrackingBitmaskNumber Theory

Problem: #2992
Pattern: Backtracking
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

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)

Complexity

Measure	Complexity
Time	O(n \times 2^n)
Space	O(2^n) auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2992. Number of Self-Divisible Permutations is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2992. Number of Self-Divisible Permutations?: LeetCode 2992. Number of Self-Divisible Permutations is rated Medium on LeetCode.
What is the time complexity of LeetCode 2992. Number of Self-Divisible Permutations?: The Python solution on this page runs in O(n \times 2^n).
What is the space complexity of LeetCode 2992. Number of Self-Divisible Permutations?: The Python solution on this page uses O(2^n) auxiliary space.
What topics does LeetCode 2992. Number of Self-Divisible Permutations cover?: LeetCode 2992. Number of Self-Divisible Permutations is tagged Bit Manipulation, Array, Math, Dynamic Programming, Backtracking, Bitmask and Number Theory on LeetCode.
Is LeetCode 2992. Number of Self-Divisible Permutations a premium problem?: Yes. LeetCode 2992. Number of Self-Divisible Permutations is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.