Problem Description

You are given an integer n. You need to find how many permutations of the array [1, 2, ..., n] are self-divisible.

A permutation is self-divisible when it satisfies a special property: for every position i (where positions are numbered from 1 to n), the greatest common divisor (GCD) of the element at position i and the position number i itself must equal 1. In mathematical terms, gcd(a[i], i) == 1 must hold for all positions.

For example, if we have n = 3, we need to check all 6 permutations of [1, 2, 3]:

• [1, 2, 3]: Check if gcd(1,1)==1, gcd(2,2)==1, gcd(3,3)==1
• [1, 3, 2]: Check if gcd(1,1)==1, gcd(3,2)==1, gcd(2,3)==1
• [2, 1, 3]: Check if gcd(2,1)==1, gcd(1,2)==1, gcd(3,3)==1
• [2, 3, 1]: Check if gcd(2,1)==1, gcd(3,2)==1, gcd(1,3)==1
• [3, 1, 2]: Check if gcd(3,1)==1, gcd(1,2)==1, gcd(2,3)==1
• [3, 2, 1]: Check if gcd(3,1)==1, gcd(2,2)==1, gcd(1,3)==1

The task is to count how many of these permutations satisfy the self-divisible property and return that count.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves permutations of an array, not nodes and edges in a graph structure.

Need to solve for kth smallest/largest?

• No: We're counting valid permutations, not finding a specific kth element.

Involves Linked Lists?

• No: The problem deals with array permutations, not linked list operations.

Does the problem have small constraints?

• Yes: Since we're dealing with permutations, the value of n must be reasonably small. Generating all permutations has factorial time complexity, which is only feasible for small values (typically n ≤ 20).

Brute force / Backtracking?

• Yes: We need to explore different permutations by placing numbers at different positions, checking the GCD constraint at each step, and backtracking when a placement doesn't work.

Conclusion: The flowchart correctly leads us to use a Backtracking approach. We need to:

1. Try placing each unused number at the current position
2. Check if the placement satisfies the GCD constraint (gcd(number, position) == 1)
3. If valid, recursively continue building the permutation
4. Backtrack when we can't proceed or have completed a valid permutation
5. Count all valid complete permutations

The solution uses state compression with bitmask to track which numbers have been used, combined with memoization to avoid recalculating the same states, making it an optimized backtracking approach.

Intuition

The key insight is that we need to build permutations position by position, and at each position, we must ensure the GCD constraint is satisfied. This naturally suggests a backtracking approach where we try placing different numbers and undo choices that don't work.

Think of it like filling slots one by one. For position 1, we try placing any unused number that satisfies gcd(number, 1) == 1. For position 2, we try placing any remaining unused number that satisfies gcd(number, 2) == 1, and so on.

However, naive backtracking would repeatedly solve the same subproblems. For instance, if we've placed numbers {1, 3, 5} at positions {2, 4, 6}, the count of valid ways to fill the remaining positions is the same regardless of how we arrived at this state. This observation leads us to use memoization.

To implement memoization efficiently, we need a way to represent which numbers have been used. A bitmask is perfect for this - if bit j is set in our mask, it means number j has been used. The state mask uniquely identifies which numbers are available, and the current position we're filling is simply mask.bit_count() + 1 (the number of bits set plus one).

The recursive function dfs(mask) answers: "Given that we've already placed some numbers (represented by mask), how many valid ways are there to complete the permutation?" We start with dfs(0) (no numbers placed) and at each step:

1. Determine the current position i we're filling
2. Try each unused number j where gcd(i, j) == 1
3. Recursively count valid completions after placing j at position i

This approach elegantly combines backtracking with dynamic programming through memoization, reducing the time complexity from factorial to something more manageable by avoiding redundant calculations.

Learn more about Math, Dynamic Programming, Backtracking and Bitmask patterns.

Solution Approach

The solution uses state compression with bitmask and memoization to efficiently count valid permutations.

State Representation:

• We use a binary number mask where the j-th bit being 1 means number j has been used
• For example, mask = 0b1010 means numbers 2 and 4 have been used (reading from right, 0-indexed)
• The current position to fill is i = mask.bit_count() + 1 (number of used numbers plus 1)

Recursive Function Design: The function dfs(mask) returns the count of valid permutations that can be formed starting from the current state:

@cache
def dfs(mask: int) -> int:
    i = mask.bit_count() + 1  # Current position to fill
    if i > n:
        return 1  # Complete valid permutation found

Core Algorithm:

1. Calculate the current position i based on how many numbers are already placed
2. If i > n, we've successfully placed all numbers - return 1
3. Otherwise, try placing each unused number j (from 1 to n):
   • Check if j is unused: (mask >> j & 1) == 0
   • Check if placement is valid: gcd(i, j) == 1
   • If both conditions met, recursively count: dfs(mask | 1 << j)

Bit Operations Explained:

• mask >> j & 1: Checks if bit j is set (number j is used)
• mask | 1 << j: Sets bit j to mark number j as used
• mask.bit_count(): Counts how many bits are set (numbers used)

Example Walkthrough: For n = 3, starting with dfs(0):

• Position 1: Try numbers 1, 2, 3
  • If placing 1: Check gcd(1, 1) == 1 ✓, recurse with mask = 0b10
  • If placing 2: Check gcd(1, 2) == 1 ✓, recurse with mask = 0b100
  • If placing 3: Check gcd(1, 3) == 1 ✓, recurse with mask = 0b1000

The @cache decorator ensures we never recalculate dfs(mask) for the same mask value, converting what would be factorial time complexity into approximately O(2^n × n) time with O(2^n) space for memoization.

Example Walkthrough

Let's trace through n = 3 to see how the algorithm works.

Initial call: dfs(0) with mask = 0b000 (no numbers used)

Step 1: Position 1 (i = 1, mask = 0b000)

• Try number 1: gcd(1,1) = 1 ✓ → Call dfs(0b010)
• Try number 2: gcd(1,2) = 1 ✓ → Call dfs(0b100)
• Try number 3: gcd(1,3) = 1 ✓ → Call dfs(0b1000)

Step 2a: Following path with 1 at position 1 (mask = 0b010)

• Position 2 (i = 2), available numbers: {2, 3}
• Try number 2: gcd(2,2) = 2 ✗ (skip)
• Try number 3: gcd(2,3) = 1 ✓ → Call dfs(0b1010)

Step 3a: Continuing (mask = 0b1010)

• Position 3 (i = 3), available numbers: {2}
• Try number 2: gcd(3,2) = 1 ✓ → Call dfs(0b1110)
• Returns 1 (all numbers placed: [1,3,2] is valid)

Step 2b: Following path with 2 at position 1 (mask = 0b100)

• Position 2 (i = 2), available numbers: {1, 3}
• Try number 1: gcd(2,1) = 1 ✓ → Call dfs(0b110)
• Try number 3: gcd(2,3) = 1 ✓ → Call dfs(0b1100)

Step 3b: From mask = 0b110

• Position 3 (i = 3), available numbers: {3}
• Try number 3: gcd(3,3) = 3 ✗ (skip)
• Returns 0 (no valid completion)

Step 3c: From mask = 0b1100

• Position 3 (i = 3), available numbers: {1}
• Try number 1: gcd(3,1) = 1 ✓ → Returns 1
• Valid permutation found: [2,3,1]

The process continues for all branches. Key observation: when we encounter dfs(0b110) again from a different path, memoization returns the cached result (0) without recomputation.

Final valid permutations found: [1,3,2] and [2,3,1], so the answer is 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × 2^n)

The algorithm uses dynamic programming with memoization through a bitmask approach. The mask parameter represents which numbers have been used in the permutation so far, with at most 2^n possible states (each of the n numbers can be either used or not used). For each state represented by the mask, we iterate through all n numbers to find valid candidates for the next position. Therefore, the total time complexity is O(n × 2^n).

Space Complexity: O(2^n)

The space complexity comes from two sources:

1. The memoization cache stores results for each unique mask state, which can have at most 2^n different values
2. The recursion stack depth is at most n (when building a complete permutation), contributing O(n) to space

Since 2^n dominates n for large values, the overall space complexity is O(2^n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Bit Indexing for Number Representation

The Pitfall: The most common mistake is confusion about how numbers are represented in the bitmask. The code uses bit position j to represent number j, which means:

• Bit 0 represents nothing (unused)
• Bit 1 represents number 1
• Bit 2 represents number 2
• And so on...

Many developers incorrectly use 0-indexed bit positions (bit 0 for number 1, bit 1 for number 2), leading to wrong results.

Wrong Implementation:

# INCORRECT: Using 0-indexed bits
for number in range(1, n + 1):
    bit_position = number - 1  # Wrong indexing!
    is_unused = (used_mask >> bit_position & 1) == 0
    if is_unused and gcd(current_position, number) == 1:
        new_mask = used_mask | (1 << bit_position)
        valid_permutations += dfs(new_mask)

Correct Solution: Keep the bit position the same as the number value. This makes the logic clearer and avoids off-by-one errors:

# CORRECT: Bit j represents number j
for number in range(1, n + 1):
    is_unused = (used_mask >> number & 1) == 0  # Bit position = number
    if is_unused and gcd(current_position, number) == 1:
        new_mask = used_mask | (1 << number)
        valid_permutations += dfs(new_mask)

2. GCD Argument Order Confusion

The Pitfall: While gcd(a, b) == gcd(b, a) mathematically, developers might confuse which argument represents the position and which represents the value, leading to logic errors when debugging or modifying the code.

Potential Confusion:

# Both work but can cause confusion about what's being checked
gcd(number, current_position) == 1  # Value first, position second
gcd(current_position, number) == 1  # Position first, value second

Best Practice: Be consistent and document your choice. The solution uses gcd(current_position, number) to match the problem statement's gcd(a[i], i) format where position comes second conceptually but we're checking if position and value are coprime.

3. Memory Optimization Oversight

The Pitfall: For larger values of n, the cache can grow to 2^n states. Without considering memory limits, this approach fails for n > 20 due to memory constraints.

Solution for Larger n: If you need to handle larger values, consider:

from functools import lru_cache

class Solution:
    def selfDivisiblePermutationCount(self, n: int) -> int:
        @lru_cache(maxsize=100000)  # Limit cache size
        def dfs(used_mask: int) -> int:
            # ... rest of the code

Or use iterative DP with careful state management to control memory usage explicitly.