LeetCode 2992 - Number of Self-Divisible Permutations

The problem asks us to count how many permutations of the numbers 1 through n satisfy a special condition called self-divisible. We start with the array: We must rearrange these numbers into every possible permutation, then determine whether the permutation is valid.

leetcodemediumarraymathdynamic-programmingbacktrackingbit-manipulationnumber-theorybitmask

LeetCode Problem 2992

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Backtracking, Bit Manipulation, Number Theory, Bitmask

Solution

Problem Understanding

The problem asks us to count how many permutations of the numbers 1 through n satisfy a special condition called self-divisible.

We start with the array:

[1, 2, 3, ..., n]

We must rearrange these numbers into every possible permutation, then determine whether the permutation is valid.

A permutation a is considered self-divisible if for every position i from 1 to n:

gcd(a[i], i) == 1

This means the value placed at index i must be coprime with the index itself. Two numbers are coprime if their greatest common divisor is 1.

For example, suppose:

a = [3, 1, 2]

Then we check:

  • gcd(3, 1) = 1
  • gcd(1, 2) = 1
  • gcd(2, 3) = 1

Since all positions satisfy the condition, this permutation is valid.

The input is a single integer n, where:

1 <= n <= 12

The output is the total number of valid self-divisible permutations.

The constraint n <= 12 is extremely important. A full permutation space has size:

n!

For n = 12:

12! = 479001600

Trying every permutation directly would be far too slow. This strongly suggests we need a smarter combinatorial or dynamic programming approach.

Some important edge cases immediately stand out:

  • n = 1, there is only one permutation.
  • Positions with many divisibility conflicts can drastically reduce valid placements.
  • Numbers sharing factors with many indices become difficult to place.
  • Because the array is 1-indexed, position handling must be careful to avoid off-by-one errors.

The problem guarantees:

  • All numbers from 1 to n are unique.
  • We always work with permutations, so every number must be used exactly once.

Approaches

Brute Force

The most direct approach is to generate all permutations of [1, 2, ..., n].

For each permutation:

  1. Iterate through every position.
  2. Compute gcd(permutation[i], i + 1).
  3. If every gcd equals 1, count the permutation.

This approach is correct because it explicitly checks every possible arrangement and verifies the required condition.

However, the complexity is enormous.

There are n! permutations, and each requires up to n gcd computations.

The total complexity becomes:

O(n! * n)

For n = 12, this is completely impractical.

Optimal Approach, Backtracking with Bitmask Dynamic Programming

The key observation is that we do not actually need to generate every permutation independently.

Instead, we can build permutations incrementally:

  • Place one number at a time.
  • Track which numbers have already been used.
  • Only continue recursion if the current placement is valid.

Because n <= 12, we can represent used numbers with a bitmask.

A bitmask lets us efficiently encode which values are already chosen:

  • Bit 0 represents number 1
  • Bit 1 represents number 2
  • and so on

This creates at most:

2^n

different states.

For each state, we only need to know:

  • which numbers are already used
  • what position we are currently filling

This naturally leads to memoized DFS or DP over subsets.

The pruning is very effective because invalid placements are rejected immediately.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n! * n) O(n) Generates every permutation explicitly
Optimal O(n * 2^n) O(2^n) Uses bitmask DP with memoization

Algorithm Walkthrough

Step 1: Precompute Valid Placements

For every position i from 1 to n, determine which numbers can legally be placed there.

A number x is valid if:

$\gcd(x,i)=1$

We store these valid numbers for each position so we do not repeatedly recompute gcd values during recursion.

For example, when n = 3:

Position Valid Numbers
1 1, 2, 3
2 1, 3
3 1, 2

Step 2: Represent Used Numbers with a Bitmask

We use an integer mask where each bit represents whether a number is already used.

Example for n = 4:

Mask Meaning
0000 no numbers used
0101 numbers 1 and 3 used
1111 all numbers used

This compact representation allows efficient memoization.

Step 3: Define the Recursive State

Define:

dfs(mask)

where:

  • mask tells us which numbers are already placed
  • the next position is determined by how many bits are set in mask

If k numbers are already used, then we are filling position:

k + 1

Step 4: Try All Valid Candidates

For the current position:

  1. Iterate through all numbers valid for that position.
  2. Skip numbers already used in the mask.
  3. Mark the number as used.
  4. Recurse to the next position.
  5. Sum all valid completions.

Step 5: Memoize Results

Many recursive paths reach the same mask.

Memoization ensures each mask is solved only once.

This reduces complexity from factorial to exponential.

Step 6: Base Case

If all numbers are used:

mask == (1 << n) - 1

then we constructed one valid permutation, so return 1.

Why it works

The algorithm explores every valid permutation exactly once.

At every recursive step:

  • only unused numbers are considered
  • only gcd-compatible placements are allowed

Therefore every generated arrangement satisfies the self-divisible condition.

Memoization preserves correctness because the number of valid completions from a given mask depends only on which numbers remain unused, not on the order used to reach that state.

Python Solution

from math import gcd
from functools import lru_cache
from typing import List

class Solution:
    def selfDivisiblePermutationCount(self, n: int) -> int:
        valid = [[] for _ in range(n + 1)]

        for position in range(1, n + 1):
            for num in range(1, n + 1):
                if gcd(position, num) == 1:
                    valid[position].append(num)

        full_mask = (1 << n) - 1

        @lru_cache(None)
        def dfs(mask: int) -> int:
            if mask == full_mask:
                return 1

            position = mask.bit_count() + 1
            total = 0

            for num in valid[position]:
                bit = 1 << (num - 1)

                if mask & bit:
                    continue

                total += dfs(mask | bit)

            return total

        return dfs(0)

The implementation begins by precomputing all valid placements for every position. This prevents repeated gcd calculations during recursion.

The valid array stores which numbers may legally appear at each index.

The recursive function dfs(mask) represents the number of valid permutations that can be formed from the current used-number state.

The next position is inferred from the number of used bits in the mask. Python's bit_count() efficiently computes this.

For each candidate number:

  • compute its bit representation
  • skip it if already used
  • recurse with the updated mask

Memoization with lru_cache ensures every mask is computed only once.

The recursion terminates when all bits are set, meaning a complete valid permutation has been formed.

Go Solution

package main

import "math/bits"

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func selfDivisiblePermutationCount(n int) int {
	valid := make([][]int, n+1)

	for pos := 1; pos <= n; pos++ {
		for num := 1; num <= n; num++ {
			if gcd(pos, num) == 1 {
				valid[pos] = append(valid[pos], num)
			}
		}
	}

	fullMask := (1 << n) - 1
	memo := make(map[int]int)

	var dfs func(int) int

	dfs = func(mask int) int {
		if mask == fullMask {
			return 1
		}

		if val, exists := memo[mask]; exists {
			return val
		}

		position := bits.OnesCount(uint(mask)) + 1
		total := 0

		for _, num := range valid[position] {
			bit := 1 << (num - 1)

			if mask&bit != 0 {
				continue
			}

			total += dfs(mask | bit)
		}

		memo[mask] = total
		return total
	}

	return dfs(0)
}

The Go implementation follows the same algorithmic structure as the Python version.

A custom gcd helper is implemented using the Euclidean algorithm.

Instead of Python's lru_cache, Go uses a map[int]int for memoization.

The number of set bits is computed using:

bits.OnesCount(uint(mask))

Go integers are sufficient because the maximum mask size is only 2^12.

Worked Examples

Example 1

Input:

n = 1

Valid placements:

Position Valid Numbers
1 1

DFS execution:

Mask Position Choices Result
0000 1 1 recurse
0001 complete none return 1

Answer:

1

Example 2

Input:

n = 2

Valid placements:

Position Valid Numbers
1 1, 2
2 1

DFS states:

Mask Position Candidate Valid
00 1 1 yes
01 2 1 already used
00 1 2 yes
10 2 1 yes

Constructed permutation:

[2, 1]

Answer:

1

Example 3

Input:

n = 3

Valid placements:

Position Valid Numbers
1 1, 2, 3
2 1, 3
3 1, 2

Recursive exploration:

Current Permutation Next Position Valid Choices
[] 1 1,2,3
[1] 2 3
[1,3] 3 2
[2] 2 1,3
[2,3] 3 1
[3] 2 1
[3,1] 3 2

Valid permutations:

[1,3,2]
[2,3,1]
[3,1,2]

Answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n * 2^n) Each mask is processed once and tries up to n candidates
Space O(2^n) Memoization stores one result per mask

There are exactly 2^n possible masks.

For each mask, we may iterate through up to n candidate numbers.

Therefore the total time complexity is:

O(n * 2^n)

This is efficient for n <= 12.

The memoization table stores one value for each mask, requiring:

O(2^n)

space.

Test Cases

sol = Solution()

assert sol.selfDivisiblePermutationCount(1) == 1  # smallest input
assert sol.selfDivisiblePermutationCount(2) == 1  # single valid permutation
assert sol.selfDivisiblePermutationCount(3) == 3  # provided example
assert sol.selfDivisiblePermutationCount(4) == 4  # additional small case
assert sol.selfDivisiblePermutationCount(5) == 28  # larger branching structure

# Repeated calls should still work because memoization is local
assert sol.selfDivisiblePermutationCount(2) == 1

# Boundary style stress test
result = sol.selfDivisiblePermutationCount(12)
assert isinstance(result, int)  # verifies algorithm handles maximum n
assert result > 0  # valid count should exist

Test Summary

Test Why
n = 1 Smallest possible input
n = 2 Verifies gcd filtering
n = 3 Matches provided example
n = 4 Tests deeper recursion
n = 5 Validates larger state space
repeated n = 2 call Ensures no stale global state
n = 12 Stress test near constraint limit

Edge Cases

One important edge case is n = 1. This is the smallest possible input and can expose incorrect base-case handling. The implementation correctly handles it because the initial recursive call immediately reaches the full-mask condition after placing the only number.

Another important edge case occurs when a position has very few valid numbers. For example, even positions cannot contain even numbers because their gcd would be at least 2. A naive implementation might continue exploring invalid branches unnecessarily. This solution precomputes valid placements and prunes impossible choices immediately.

A third subtle edge case involves bitmask indexing. Numbers range from 1 to n, but bit positions range from 0 to n - 1. Off-by-one errors are very common here. The implementation consistently maps number x to bit:

1 << (x - 1)

which guarantees correct tracking of used values.

Another edge case is the maximum constraint n = 12. A brute-force permutation generator would be infeasible. The memoized bitmask DP handles this efficiently because the total number of states is only:

$2^{12}=4096$

which is very manageable.