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

Special Permutations

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array nums containing n distinct positive integers. A permutation of nums is called special if for all indexes 0 <= i < n - 1, either nums[i] % nums[i+1] == 0 or nums[i+1] % nums[i] == 0. Return the total number of special permutations, modulo 10^9 + 7.

Key Insights

  • A special permutation requires each adjacent pair of numbers to have a divisibility relationship.
  • The maximum length of nums is 14, allowing for combinatorial approaches such as backtracking or dynamic programming.
  • Utilizing bit masking can help track which numbers have been used in the current permutation.

Space and Time Complexity

Time Complexity: O(n! * n)
Space Complexity: O(n)

Solution

To solve the problem, we can employ a backtracking algorithm that generates all permutations of the input array while checking the special condition on-the-fly. We can use a bitmask to track which integers from nums have already been included in the current permutation. For each integer added to the current permutation, we will ensure it satisfies the special condition with the last integer in the current sequence.

  1. Start with an empty permutation and a bitmask to track used numbers.
  2. For each number in nums, check if it can be added to the current permutation based on the special condition.
  3. If it can be added, mark it as used, recursively build the next state, and once a valid permutation is formed, count it.
  4. Finally, return the count of all valid special permutations modulo 10^9 + 7.

Code Solutions

def countSpecialPermutations(nums):
    MOD = 10**9 + 7
    n = len(nums)
    
    # Create a mask to keep track of used numbers
    dp = [[-1] * (1 << n) for _ in range(n)]
    
    def is_special(a, b):
        return a % b == 0 or b % a == 0
    
    def backtrack(pos, mask):
        if mask == (1 << n) - 1:  # All numbers are used
            return 1
        
        if dp[pos][mask] != -1:
            return dp[pos][mask]
        
        count = 0
        for i in range(n):
            if not (mask & (1 << i)):  # If nums[i] is not used
                if pos == -1 or is_special(nums[pos], nums[i]):
                    count = (count + backtrack(i, mask | (1 << i))) % MOD
        
        dp[pos][mask] = count
        return count
    
    return backtrack(-1, 0)

# Example usage:
print(countSpecialPermutations([2, 3, 6]))  # Output: 2
print(countSpecialPermutations([1, 4, 3]))  # Output: 2
← Back to All Questions