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 a gcd of 1 with i. So during permutation generation, we can only place a number at i 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 the i-th bit of mask is 1 if the number i has already been used, otherwise it is 0.

• 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 current mask 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 the mask (tracked by mask.bit_count() + 1) exceeds n, it means that every number from 1 to n has been placed in the permutation. Hence, we found a valid permutation and return 1.

• Recursive Case: If we haven't built a full permutation, we iterate through all potential numbers j from 1 to n. For each number, we check two conditions:

  1. j is not yet used in the current mask state ((mask >> j & 1) == 0).
  2. Placing j at the current index i maintains the self-divisible property (gcd(a[i], i) == 1), i.e., either i % j == 0 or j % i == 0.

  If both conditions are met, we recursively call dfs(mask | 1 << j), which represents the new state after including j 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 number j is already used.
• mask | 1 << j updates the state to include number j.

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.

Example 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).

1. Start with an empty permutation (mask = 0) which means that no number has been used yet in our permutation.

2. Call dfs(0) to explore permutations. Since no numbers are used yet, mask.bit_count() + 1 is 1, which is our current index i.

3. Now look to place numbers [1, 2, 3] at index i = 1. Since the gcd of 1 with any number is always 1, all numbers [1, 2, 3] can be placed at the first index.

   • Choosing 1 for index i = 1, the new mask becomes 0b001. Call dfs(0b001) to continue building the permutation from here.
   • Choosing 2 for index i = 1, the new mask becomes 0b010. Call dfs(0b010).
   • Choosing 3 for index i = 1, the new mask becomes 0b100. Call dfs(0b100).

4. Each of these calls to dfs represents a different branch in our exploration of permutations. Let's consider just one branch, say dfs(0b001), where 1 is at index 1.

5. Using dfs(0b001) as the current state, mask.bit_count() + 1 is 2, which is our new index i. Try placing 2 and 3 at index 2:

   • We cannot place 2 at index 2 since gcd(2, 2) is not 1.
   • We can place 3 because gcd(3, 2) is 1. The new mask is 0b101. Call dfs(0b101).

6. With dfs(0b101), we are at mask.bit_count() + 1 = 3, which is the last index. With 1 and 3 already used, only 2 is left, and it can be placed at index 3 because gcd(3, 2) is 1. This completes this permutation [1, 3, 2], so dfs(0b101) returns 1.

7. Similarly, explore other branches such as dfs(0b010) and dfs(0b100), and for each complete valid permutation found, add 1 to our total count.

8. Apply memoization to remember the results of dfs(mask) for every unique mask. This way, if we encounter the same mask again in a different branch, we don't recompute the results.

9. 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

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 length n 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 factor n.
• 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 the 2^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 the 2^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.