Number of Self-Divisible Permutations

Number of Self-Divisible Permutations

What is this problem about?

The Number of Self-Divisible Permutations problem asks you to count permutations of numbers 1 to n where for each position i, perm[i] is divisible by i (1-indexed). This coding problem uses bitmask DP to count valid assignments where each position's divisibility constraint is satisfied.

Why is this asked in interviews?

Salesforce asks this to test bitmask DP with divisibility constraints — a variant of the assignment problem. For small n, enumerate all permutations using backtracking with bitmask state. The array, math, number theory, bitmask, backtracking, bit manipulation, and dynamic programming interview pattern is the core.

Algorithmic pattern used

Bitmask DP. dp[mask] = number of ways to assign values to the first popcount(mask) positions using exactly the values indicated by the set bits in mask. For each position i (= popcount(mask) + 1), try each unused value v (bit not in mask): if v % i == 0, update dp[mask | (1<<(v-1))] += dp[mask]. Answer = dp[(1<<n) - 1].

Example explanation

n=3. Check permutations of [1,2,3] where perm[1]%1==0, perm[2]%2==0, perm[3]%3==0.

• Position 1: any value (all divisible by 1): options 1,2,3.
• Position 2: must be divisible by 2: only 2. So perm[2]=2.
• Position 3: must be divisible by 3: only 3. So perm[3]=3.
• perm[1]: remaining is 1. Only valid permutation: [1,2,3]. Count = 1.

Common mistakes candidates make

• Using 1-indexed vs 0-indexed positions inconsistently.
• Not checking divisibility correctly: value % position == 0.
• Brute-force O(n!) permutation generation for large n.
• Off-by-one in bitmask indexing (value v maps to bit v-1).

Interview preparation tip

Bitmask DP assignment problems follow the template: dp[mask] = ways to assign elements to the first k positions (k = popcount(mask)) using exactly the elements in mask. Transition: try each unused element as the next assignment, check constraints, update. The key constraint here is divisibility. Practice the Traveling Salesman Problem bitmask DP first, then adapt to assignment constraints like this one.