In this guide, you will get 2741. Special Permutations LeetCode Solution with the best time and space complexity. The solution to Special Permutations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity: O(n^2 \cdot 2^n)
Space Complexity: O(n \cdot 2^n)
2741. Special Permutations LeetCode Solution in C++
class Solution {
public:
int specialPerm(vector<int>& nums) {
const int n = nums.size();
const int maxMask = 1 << n;
int ans = 0;
vector<vector<int>> mem(n, vector<int>(maxMask));
for (int i = 0; i < n; ++i) {
ans += specialPerm(nums, i, 1 << i, maxMask, mem);
ans %= kMod;
}
return ans;
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of special permutations, where the previous number is
// nums[i] and `mask` is the bitmask of the used numbers.
int specialPerm(const vector<int>& nums, int prev, int mask,
const int& maxMask, vector<vector<int>>& mem) {
if (mask == maxMask - 1)
return 1;
if (mem[prev][mask] > 0)
return mem[prev][mask];
int res = 0;
for (int i = 0; i < nums.size(); ++i) {
if (mask >> i & 1)
continue;
if (nums[i] % nums[prev] == 0 || nums[prev] % nums[i] == 0) {
res += specialPerm(nums, i, mask | 1 << i, maxMask, mem);
res %= kMod;
}
}
return mem[prev][mask] = res;
}
}; /* code provided by PROGIEZ */
2741. Special Permutations LeetCode Solution in Java
class Solution {
public int specialPerm(int[] nums) {
final int n = nums.length;
final int maxMask = 1 << n;
int ans = 0;
int[][] mem = new int[n][maxMask];
for (int i = 0; i < n; ++i) {
ans += specialPerm(nums, i, 1 << i, maxMask, mem);
ans %= kMod;
}
return ans;
}
private static final int kMod = 1_000_000_007;
// Returns the number of special permutations, where the previous number is
// nums[i] and `mask` is the bitmask of the used numbers.
private int specialPerm(int[] nums, int prev, int mask, int maxMask, int[][] mem) {
if (mask == maxMask - 1)
return 1;
if (mem[prev][mask] != 0)
return mem[prev][mask];
int res = 0;
for (int i = 0; i < nums.length; ++i) {
if ((mask >> i & 1) == 1)
continue;
if (nums[i] % nums[prev] == 0 || nums[prev] % nums[i] == 0) {
res += specialPerm(nums, i, mask | 1 << i, maxMask, mem);
res %= kMod;
}
}
return mem[prev][mask] = res;
}
} // code provided by PROGIEZ
2741. Special Permutations LeetCode Solution in Python
class Solution:
def specialPerm(self, nums: list[int]) -> int:
kMod = 1_000_000_007
maxMask = 1 << len(nums)
@functools.lru_cache(None)
def dp(prev: int, mask: int) -> int:
"""
Returns the number of special permutations, where the previous number is
nums[i] and `mask` is the bitmask of the used numbers.
"""
if mask == maxMask - 1:
return 1
res = 0
for i, num in enumerate(nums):
if mask >> i & 1:
continue
if num % nums[prev] == 0 or nums[prev] % num == 0:
res += dp(i, mask | 1 << i)
res %= kMod
return res
return sum(dp(i, 1 << i)
for i in range(len(nums))) % kMod # code by PROGIEZ
