Watch 3 video solutions for Number of Self-Divisible Permutations, a medium level problem involving Array, Dynamic Programming, Backtracking. This walkthrough by Huifeng Guan has 305 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 12Problem 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 | 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 |