LeetCode Solutions Blog

Special Permutations

Number: 2848

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array of distinct positive integers, count the number of permutations such that for every adjacent pair, either the left element is divisible by the right element or vice versa. The answer should be computed modulo 10^9 + 7.

Key Insights

Use Dynamic Programming with Bitmasking to explore all permutations.
The state dp[mask][i] represents the number of ways to form a permutation ending at index i using the set of elements indicated by mask.
Precompute a 2D boolean matrix to quickly check the divisibility condition between any two numbers.
The small input size (n <= 14) makes a 2^n * n DP feasible.

Space and Time Complexity

Time Complexity: O(n^2 * 2^n) Space Complexity: O(n * 2^n)

Solution

We use Bitmask Dynamic Programming. First, we precompute a matrix valid such that valid[i][j] is true if either nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0. We then initialize a dp table with dimensions (1 << n) x n where each dp[mask][i] holds the number of ways to form a permutation ending with element i using indices in mask. The recurrence extends the current permutation by trying all unused elements that satisfy the special condition with the current last element. Finally, we sum the ways for the full mask over all ending indices and return the result modulo 10^9+7.

Code Solutions

# Python implementation
MOD = 10**9 + 7

def specialPermutations(nums):
    n = len(nums)
    # Precompute the valid connectivity matrix
    valid = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j:
                # Check if either divides the other
                if nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0:
                    valid[i][j] = True

    # dp[mask][i]: ways to form permutation with indices in mask finishing with index i
    dp = [[0] * n for _ in range(1 << n)]
    # Initialization: start permutation with each number
    for i in range(n):
        dp[1 << i][i] = 1

    # Iterate over all masks
    for mask in range(1 << n):
        for last in range(n):
            # If last is in current mask and there exists a valid count 
            if (mask & (1 << last)) and dp[mask][last] > 0:
                # Try adding any index j that is not in mask
                for j in range(n):
                    if mask & (1 << j) == 0 and valid[last][j]:
                        dp[mask | (1 << j)][j] = (dp[mask | (1 << j)][j] + dp[mask][last]) % MOD

    # Sum up the results for the mask with all elements used
    full_mask = (1 << n) - 1
    result = sum(dp[full_mask][i] for i in range(n)) % MOD
    return result

# Example usage:
nums = [2, 3, 6]
print(specialPermutations(nums))  # Expected output: 2