Number of Self-Divisible Permutations - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: Given n, build permutations of numbers 1..n. A permutation is valid if the value placed at position i is divisible by i. The task is to count how many such permutations exist.
Approach 1: State Compression + Memoization Search (Backtracking + Bitmask) (Time: O(n * 2^n), Space: O(2^n))
This approach constructs the permutation position by position using backtracking. A bitmask tracks which numbers from 1..n are already used. At position i, iterate through all numbers not used in the mask and only place values where num % i == 0. The mask becomes the memoization key, allowing the algorithm to cache the number of valid completions for each state and avoid recomputation.
The key insight: the order of previously placed numbers doesn't matter once the set of used numbers is known. That makes mask sufficient to represent the state. Memoization reduces the exponential search from factorial permutations to roughly n * 2^n states. This pattern appears frequently in backtracking problems with subset states.
Approach 2: State Compression + Dynamic Programming (Bitmask DP) (Time: O(n * 2^n), Space: O(2^n))
The dynamic programming formulation iterates over all subset states. Let dp[mask] represent the number of valid ways to build a partial permutation using the numbers indicated in mask. The current position is derived from the number of set bits in the mask (pos = popcount(mask) + 1). For each unused number num, check the divisibility condition num % pos == 0. If valid, transition to dp[mask | (1 << (num-1))].
This transforms the recursive search into iterative transitions across all subsets. Bit operations make checking and updating states constant time, which is why bitmask techniques are ideal here. The DP version is often easier to reason about for people comfortable with subset iteration and dynamic programming.
Recommended for interviews: Start by describing the backtracking solution to show you understand the permutation constraints. Then optimize it with memoization using a bitmask state. Interviewers typically expect the state compression DP idea because it reduces factorial complexity to O(n * 2^n) and demonstrates strong understanding of subset DP patterns.
Approach 1: State Compression + Memoization Search
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.
Code
Python
Java
C++
Go
TypeScript
Approach 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| State Compression + Memoization Search | ā |
| State Compression + Dynamic Programming | ā |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking + Memoization (Bitmask) | O(n * 2^n) | O(2^n) | Best when solving recursively and caching subset states to prune repeated work |
| Bitmask Dynamic Programming | O(n * 2^n) | O(2^n) | Preferred when you want an iterative subset DP formulation |
Video Solution
2992. Number of Self-Divisible Permutations (Leetcode Medium) ā¢ Programming Live with Larry ā¢ 267 views views
Frequently Asked Questions
Is Number of Self-Divisible Permutations easy or hard?
Number of Self-Divisible Permutations Python/Java solution
How to solve Number of Self-Divisible Permutations in O(n * 2^n)?
What is the best approach for Number of Self-Divisible Permutations?
Is Number of Self-Divisible Permutations asked at Google/Amazon/Meta?
What data structure is used in Number of Self-Divisible Permutations?
What is the time complexity of Number of Self-Divisible Permutations?
Ready to solve this problem?
Practice Number of Self-Divisible Permutations with our built-in code editor and test cases.
Practice on FleetCode