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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

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

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


Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄