Scale Engineer

Special Permutations

Med
#2466Time: O(n! * n) - There are `n!` possible permutations to generate. For each permutation, we take O(n) time to check if it's special. This makes the approach infeasible for `n > 10`.Space: O(n) - The space is dominated by the recursion stack depth and the list used to store the current permutation, both of which can go up to size `n`.
Patterns
Dynamic ProgrammingBit ManipulationBitmask
Data structures
Array

Prompt

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. As the answer could be large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [2,3,6]
Output: 2
Explanation: [3,6,2] and [2,6,3] are the two special permutations of nums.

Example 2:

Input: nums = [1,4,3]
Output: 2
Explanation: [3,1,4] and [4,1,3] are the two special permutations of nums.

 

Constraints:

  • 2 <= nums.length <= 14
  • 1 <= nums[i] <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible arrangement (permutation) of the nums array. For each generated permutation, it performs a check to see if it satisfies the "special" condition. If it does, a counter is incremented. This method is the most straightforward to conceptualize but is computationally very expensive.

Algorithm

  • Initialize a counter count to 0.
  • Create a recursive helper function, generatePermutations(nums, current_permutation, used_flags), to generate all permutations of nums.
  • The function works as follows:
    • Base Case: If the current_permutation has n elements, it's a complete permutation. Check if it's a special permutation using a helper function isSpecial().
    • If it is special, increment the count (with modulo arithmetic).
    • Recursive Step: Iterate through each number in the original nums array. If a number hasn't been used, mark it as used, add it to current_permutation, and make a recursive call. After the call returns, backtrack by removing the number and unmarking it.
  • The isSpecial(permutation) helper function iterates from i = 0 to n-2 and checks if perm[i] % perm[i+1] == 0 or perm[i+1] % perm[i] == 0 for all adjacent pairs. If any pair fails this condition, it returns false.
  • Start the process by calling generatePermutations with an empty permutation.
  • Return the final count.

Walkthrough

The core idea is to explore all n! permutations of the input array. We can use a recursive helper function to build these permutations. The function maintains a list for the current permutation being built and a boolean array to keep track of which numbers from the original array have been used.

Once a full permutation of length n is formed, we validate it. The validation involves iterating through the permutation from the first to the second-to-last element and checking the divisibility condition for each adjacent pair (nums[i] and nums[i+1]). If all pairs in the permutation satisfy the condition, we increment our total count of special permutations. Since the answer can be large, the count is maintained modulo 10^9 + 7.

class Solution {    long count = 0;    int MOD = 1_000_000_007;     public int specialPerm(int[] nums) {        List<Integer> p = new ArrayList<>();        boolean[] used = new boolean[nums.length];        generatePermutations(nums, p, used);        return (int) count;    }     private void generatePermutations(int[] nums, List<Integer> p, boolean[] used) {        if (p.size() == nums.length) {            if (isSpecial(p)) {                count = (count + 1) % MOD;            }            return;        }         for (int i = 0; i < nums.length; i++) {            if (!used[i]) {                used[i] = true;                p.add(nums[i]);                generatePermutations(nums, p, used);                p.remove(p.size() - 1); // Backtrack                used[i] = false;            }        }    }     private boolean isSpecial(List<Integer> p) {        for (int i = 0; i < p.size() - 1; i++) {            if (p.get(i) % p.get(i + 1) != 0 && p.get(i + 1) % p.get(i) != 0) {                return false;            }        }        return true;    }}

Complexity

Time

O(n! * n) - There are `n!` possible permutations to generate. For each permutation, we take O(n) time to check if it's special. This makes the approach infeasible for `n > 10`.

Space

O(n) - The space is dominated by the recursion stack depth and the list used to store the current permutation, both of which can go up to size `n`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for very small values of n.

Cons

  • Extremely inefficient due to its factorial time complexity.

  • Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for constraints like n=14.

Solutions

class Solution {public  int specialPerm(int[] nums) {    final int mod = (int)1 e9 + 7;    int n = nums.length;    int m = 1 << n;    int[][] f = new int[m][n];    for (int i = 1; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if ((i >> j & 1) == 1) {          int ii = i ^ (1 << j);          if (ii == 0) {            f[i][j] = 1;            continue;          }          for (int k = 0; k < n; ++k) {            if (nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0) {              f[i][j] = (f[i][j] + f[ii][k]) % mod;            }          }        }      }    }    int ans = 0;    for (int x : f[m - 1]) {      ans = (ans + x) % mod;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem