2992. Number of Self-Divisible Permutations
Problem Description
Given a number n
, the task is to calculate the total number of unique permutations of an array that starts from 1
and ends with n
(inclusively), where the array's indexes are also 1-based. Such an array can be described as nums = [1, 2, ..., n]
. A permutation of this array is considered "self-divisible" if for every index i
ranging from 1 to n
, the greatest common divisor (gcd
) between the number at index i
(namely a[i]
) and the index i
itself is 1
. In simpler terms, each number at index i
must not share any common factors with i
other than 1
.
To put this into perspective, given the array [1, 2, 3]
, there are overall six permutations. Among these, the permutation [2, 3, 1]
is not self-divisible because for i = 2
, gcd(3, 2)
is not 1
. The problem is to count only those permutations that meet the self-divisible condition.
Intuition
To tackle the problem, we can use several key concepts: permutation generation, the greatest common divisor (gcd) property, bit manipulation, and memoization.
-
Permutation Generation: Generally, to generate permutations, we pick each number, place it at the current position, and recursively generate permutations for the remaining numbers. However, we need to consider only self-divisible permutations, which adds a constraint.
-
GCD Property: We must ensure that for every chosen position
i
, the number placed at that position should have agcd
of1
withi
. So during permutation generation, we can only place a number ati
if it's not already taken and it satisfies the given self-divisible condition. -
Bit Manipulation: To efficiently track which numbers have been used in the permutation so far, we use bit manipulation. A binary number
mask
is employed to represent the state of the permutation, where thei
-th bit ofmask
is1
if the numberi
has already been used, otherwise it is0
. -
Memoization and DFS: As we explore permutations, we can end up recalculating the same state multiple times. To optimize this, we can use memoizationāa method of storing already-calculated results to avoid repeated computations. A memoized depth-first search (
dfs
) function is written, which calculates the number of valid permutations that can still be formed from the currentmask
state.
The overall intuition is to represent the state of permutation as a binary number and use a recursive dfs
function, together with memoization to calculate the total number of valid self-divisible permutations. Starting with an empty permutation (mask = 0
), the dfs
function explores all possible placements of numbers that maintain the self-divisible property and sums up the total number of valid permutations from each state until the entire permutation is built (i > n
).
Learn more about Recursion, Dynamic Programming and Bitmask patterns.
Solution Approach
The solution to the problem leverages a recursive function paired with memoization to calculate the number of self-divisible permutations.
Recursive Depth-First Search (DFS) with State Compression
In the given solution, we define a recursive helper function named dfs
, which takes an integer input mask
. This mask is a binary representation of the state of the permutation being built, where each bit corresponds to whether a number has already been used in the permutation (1
for used, 0
for not used).
-
Base Case: When the number of bits set to
1
in themask
(tracked bymask.bit_count() + 1
) exceedsn
, it means that every number from1
ton
has been placed in the permutation. Hence, we found a valid permutation and return1
. -
Recursive Case: If we haven't built a full permutation, we iterate through all potential numbers
j
from1
ton
. For each number, we check two conditions:j
is not yet used in the currentmask
state ((mask >> j & 1) == 0
).- Placing
j
at the current indexi
maintains the self-divisible property (gcd(a[i], i) == 1
), i.e., eitheri % j == 0
orj % i == 0
.
If both conditions are met, we recursively call
dfs(mask | 1 << j)
, which represents the new state after includingj
in the permutation.
We keep an accumulator ans
which adds up the results from each recursive call, and it represents the total valid permutations for the current mask
.
Memoization
Memoization is used here to optimize the recursive solution. It reduces the time complexity by avoiding recomputation of dfs
for the same mask
. The @cache
decorator from Python's functools
module is used above the dfs
function, and it automagically takes care of storing and retrieving previously computed values for dfs(mask)
.
Bit Manipulation
The solution uses bitwise operations for efficient state manipulation and checking:
mask >> j & 1
checks if the numberj
is already used.mask | 1 << j
updates the state to include numberj
.
By combining recursion, memoization, and bit manipulation, the code systematically explores all permutations that satisfy the self-divisible property without redundant calculations.
Finally, we call dfs(0)
to start the process with an empty permutation and return the total number of valid permutations as the result.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach by considering n
to be 3
. This means we have an array [1, 2, 3]
, and we want to calculate the number of unique permutations where the index and the number at that index are co-prime (i.e., have a gcd of 1).
-
Start with an empty permutation (
mask = 0
) which means that no number has been used yet in our permutation. -
Call
dfs(0)
to explore permutations. Since no numbers are used yet,mask.bit_count() + 1
is1
, which is our current indexi
. -
Now look to place numbers
[1, 2, 3]
at indexi = 1
. Since thegcd
of1
with any number is always1
, all numbers[1, 2, 3]
can be placed at the first index.- Choosing
1
for indexi = 1
, the newmask
becomes0b001
. Calldfs(0b001)
to continue building the permutation from here. - Choosing
2
for indexi = 1
, the newmask
becomes0b010
. Calldfs(0b010)
. - Choosing
3
for indexi = 1
, the newmask
becomes0b100
. Calldfs(0b100)
.
- Choosing
-
Each of these calls to
dfs
represents a different branch in our exploration of permutations. Let's consider just one branch, saydfs(0b001)
, where1
is at index1
. -
Using
dfs(0b001)
as the current state,mask.bit_count() + 1
is2
, which is our new indexi
. Try placing2
and3
at index2
:- We cannot place
2
at index2
sincegcd(2, 2)
is not1
. - We can place
3
becausegcd(3, 2)
is1
. The newmask
is0b101
. Calldfs(0b101)
.
- We cannot place
-
With
dfs(0b101)
, we are atmask.bit_count() + 1 = 3
, which is the last index. With1
and3
already used, only2
is left, and it can be placed at index3
becausegcd(3, 2)
is1
. This completes this permutation[1, 3, 2]
, sodfs(0b101)
returns1
. -
Similarly, explore other branches such as
dfs(0b010)
anddfs(0b100)
, and for each complete valid permutation found, add1
to our total count. -
Apply memoization to remember the results of
dfs(mask)
for every uniquemask
. This way, if we encounter the samemask
again in a different branch, we don't recompute the results. -
Sum up all the valid permutations found to get the final answer.
For n = 3
, there are a total of 3 self-divisible permutations: [1, 3, 2]
, [2, 1, 3]
, and [3, 1, 2]
. The algorithm we discussed above would calculate this number correctly by exploring all valid possibilities while avoiding unnecessary recomputations thanks to memoization.
Solution Implementation
1class Solution:
2 def selfDivisiblePermutationCount(self, n: int) -> int:
3 from functools import lru_cache
4
5 # Use lru_cache decorator to memoize results of the DFS function
6 # This helps to avoid recalculating results for the same subproblems
7 @lru_cache(maxsize=None)
8 def dfs(current_mask: int) -> int:
9 # Calculate the position/index of the current number being placed
10 position = bin(current_mask).count("1") + 1
11
12 # If all positions are filled, return 1 as this represents a valid permutation
13 if position > n:
14 return 1
15
16 # Initialize count of valid permutations starting with the current mask
17 count = 0
18
19 # Iterate through numbers from 1 to n to try placing them at the current position
20 for number in range(1, n + 1):
21 # Check if the number is not already used (not present in current_mask)
22 # And satisfies the divisible condition (either position divisible by number or vice versa)
23 if (current_mask >> number) & 1 == 0 and (position % number == 0 or number % position == 0):
24 # Update mask to include the current number
25 # and recurse to calculate permutations with the updated mask
26 next_mask = current_mask | (1 << number)
27 count += dfs(next_mask)
28
29 # Return the count of valid permutations for the current mask
30 return count
31
32 # Start the DFS from an empty mask (no numbers used)
33 return dfs(0)
34
1class Solution {
2 private int totalNumbers; // Total number of integers in the permutation
3 private Integer[] memoizationCache; // A cache for memoization to store intermediate results
4
5 // Method to calculate the count of self-divisible permutations
6 public int selfDivisiblePermutationCount(int n) {
7 this.totalNumbers = n;
8 // The size of the memoization cache is based on the possible number of unique states,
9 // which is 2^(n+1) because we have n integers and each integer can either be used or not used.
10 memoizationCache = new Integer[1 << (n + 1)];
11 return dfs(0); // Start the depth-first search with an initial mask of 0 (no numbers used)
12 }
13
14 // Recursive depth-first search method to explore all possible permutations
15 private int dfs(int mask) {
16 // If the current state is already computed, return the cached value
17 if (memoizationCache[mask] != null) {
18 return memoizationCache[mask];
19 }
20
21 // Get the index of the next integer to place by counting the number of set bits in the mask
22 int currentIndex = Integer.bitCount(mask) + 1;
23
24 // Base case: if all integers are used, return 1 as this represents a valid permutation
25 if (currentIndex > totalNumbers) {
26 return 1;
27 }
28
29 // Initialize the current state's permutation count to 0
30 memoizationCache[mask] = 0;
31
32 // For each integer from 1 to n, try to use the integer j if it's not already used
33 // and either currentIndex is divisible by j or j is divisible by currentIndex
34 for (int j = 1; j <= totalNumbers; ++j) {
35 // Check if the bit for the j-th number is not set (0), and it's a self-divisible pair
36 if ((mask >> j & 1) == 0 && (currentIndex % j == 0 || j % currentIndex == 0)) {
37 // Increment the count for the current state by the number of permutations
38 // resulting from setting the bit for the j-th number (adding j to the current permutation)
39 memoizationCache[mask] += dfs(mask | 1 << j);
40 }
41 }
42
43 // Return the final count for the current mask (state)
44 return memoizationCache[mask];
45 }
46}
47
1#include <functional>
2#include <cstring>
3
4class Solution {
5public:
6 // Function to count the number of self-divisible permutations of length 'n'
7 int selfDivisiblePermutationCount(int n) {
8 // Create a dp array to store intermediate results,
9 // with a size based on the max possible combination of 'n' digits: 2 to the power of n
10 int dp[1 << (n + 1)];
11 // Initialize all elements of the dp array to -1
12 memset(dp, -1, sizeof(dp));
13
14 // Define a recursive lambda function for depth-first search
15 std::function<int(int)> dfs = [&](int mask) {
16 // Check if the current mask is already computed
17 if (dp[mask] != -1) {
18 return dp[mask];
19 }
20
21 // Calculate the current position using the number of set bits in mask
22 int i = __builtin_popcount(mask) + 1;
23
24 // If we have processed all positions, it's a valid permutation
25 if (i > n) {
26 return 1;
27 }
28
29 // Initialize the current mask value in dp array to 0
30 dp[mask] = 0;
31
32 // Iterate over the range 1 to n to try placing each number at the ith position
33 for (int j = 1; j <= n; ++j) {
34 // (mask >> j & 1) checks if the j-th bit is set in mask (if j has been placed)
35 // (i % j == 0 || j % i == 0) checks the self-divisible condition
36 if ((mask >> j & 1) == 0 && (i % j == 0 || j % i == 0)) {
37 // Recur with the updated mask (with the j-th bit set) to continue building the permutation
38 dp[mask] += dfs(mask | 1 << j);
39 }
40 }
41
42 // Return the number of permutations starting with the current mask configuration
43 return dp[mask];
44 };
45
46 // Start the depth-first search with an initial mask of 0 representing an empty permutation
47 return dfs(0);
48 }
49};
50
1function selfDivisiblePermutationCount(n: number): number {
2 // Initialize memoization array with a length of 2^(n+1), filled with -1, indicating uncomputed states
3 const memo: number[] = Array(1 << (n + 1)).fill(-1);
4
5 // Define the depth-first search function that will compute the count of self-divisible permutations
6 const dfs = (mask: number): number => {
7 // If the value for this bitmask has already been computed, return it to avoid redundant calculations
8 if (memo[mask] !== -1) {
9 return memo[mask];
10 }
11
12 // Calculate the position index based on the bit count of the mask
13 const positionIndex = bitCount(mask) + 1;
14
15 // When all positions are filled, return 1 as this is a valid permutation
16 if (positionIndex > n) {
17 return 1;
18 }
19
20 // Start count at 0 for the current mask
21 memo[mask] = 0;
22
23 // Iterate through potential digits [1..n] to find self-divisible candidates
24 for (let digit = 1; digit <= n; ++digit) {
25 const digitBit = 1 << digit;
26
27 // Check if the digit has not been used already and satisfies self-divisibility conditions
28 if ((mask & digitBit) === 0 && (digit % positionIndex === 0 || positionIndex % digit === 0)) {
29 // Recur with the updated mask including the current digit and accumulate the result
30 memo[mask] += dfs(mask | digitBit);
31 }
32 }
33 return memo[mask];
34 };
35
36 // Begin the recursion with an empty mask (initially no digits are used)
37 return dfs(0);
38}
39
40function bitCount(i: number): number {
41 // Perform bit operations to count the active (1's) bits in the integer
42 i = i - ((i >>> 1) & 0x55555555);
43 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
44 i = (i + (i >>> 4)) & 0x0f0f0f0f;
45 i = i + (i >>> 8);
46 i = i + (i >>> 16);
47
48 // Return the count of active bits, masked to keep the result to 6 bits
49 return i & 0x3f;
50}
51
Time and Space Complexity
The given Python code defines a function selfDivisiblePermutationCount
which counts the permutations of size n
where the i-th
position is divisible by i
or vice versa. It uses a depth-first search (DFS) approach with memoization to compute the count. Here's an analysis of its time and space complexity:
Time Complexity
The time complexity of the code is O(n * 2^n)
. This is because the algorithm explores each possible state of permutation using bit-masking. Here's a breakdown of how this complexity arises:
- There are
2^n
possible states for a permutation of lengthn
if we represent the inclusion or exclusion of each element in the permutation as a bit in a bitmask. - For each state, the code iterates through all
n
possible next numbers to include in the permutation. Hence the factorn
. - The
dfs
function is called once for each state that has not been visited before. The use of memoization ensures that each state is computed only once. - Therefore, the number of operations is proportional to the number of states times the number of possible next steps, giving us
n * 2^n
.
Space Complexity
The space complexity of the code is O(2^n)
. This accounts for the storage required for memoization of the intermediate results. Here's the rationale:
- The memoization, implemented using the
@cache
decorator, stores results for each of the2^n
possible states of the permutation. - The
dfs
function uses a bitmask to represent the state, which is an integer. Storing results for each state requires space proportional to the number of states. - The space used by the call stack during recursion is bounded by
n
(the maximum depth of recursion), but this does not dominate the2^n
space required for memoization. - Hence, the space complexity is dominated by the memoization cache, leading to
O(2^n)
space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be
Want a Structured Path to Master System Design Too? Donāt Miss This!