We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Self-Divisible Permutations

Number: 3294

Difficulty: Medium

Paid? Yes

Companies: Salesforce, Quip (Salesforce)

Problem Description

Given an integer n, return the number of permutations of the 1-indexed array nums = [1, 2, ..., n] such that the permutation is self-divisible. An array is self-divisible if for every index i (1 <= i <= n), the greatest common divisor (gcd) of the element at that index and the index itself equals 1.

Key Insights

  • Use backtracking to generate permutations while enforcing the self-divisible condition.
  • Use bitmasking to track the numbers used so far.
  • Use memoization (dynamic programming) to avoid redundant processing.
  • With n <= 12, the state-space (n * 2^n) is acceptable.

Space and Time Complexity

Time Complexity: O(n * 2^n) in the worst case since each state is derived from a bitmask of n bits. Space Complexity: O(2^n) for the memoization cache, plus O(n) for recursion stack.

Solution

We use a DFS (Depth-First Search) based backtracking approach enhanced with bitmasking to represent which numbers have been used so far. For each recursive call, the current position in the permutation is determined by the number of bits set in the bitmask. For each number not yet used, we check if the gcd of the number and the current position (1-indexed) equals 1. If it does, we mark the number as used (by setting the corresponding bit) and recursively process the next position. We employ memoization to cache the result of each bitmask state, ensuring that each state is computed only once, drastically reducing the number of recursive calls.

Code Solutions

Below are solutions in Python, JavaScript, C++, and Java with detailed line-by-line comments.

from math import gcd

def selfDivisiblePermutations(n):
    # dp dictionary to cache results for each mask
    dp = {}
    
    # Define the DFS function with current mask and position index (0-indexed for used count)
    def dfs(mask, pos):
        # base case: when mask has all n bits set, a full permutation is formed
        if mask == (1 << n) - 1:
            return 1
        # if this state has already been computed, return the cached result
        if mask in dp:
            return dp[mask]
            
        count = 0
        # Try every number from 1 to n
        for num in range(1, n + 1):
            bit = 1 << (num - 1)
            # if the number 'num' has not been used in current permutation
            if mask & bit == 0:
                # pos + 1 gives the current 1-indexed position
                if gcd(num, pos + 1) == 1:
                    count += dfs(mask | bit, pos + 1)
        dp[mask] = count
        return count
    
    return dfs(0, 0)

# Example usage:
print(selfDivisiblePermutations(3))  # Expected output: 3
← Back to All Questions