#2741

Special Permutations

expert · 1130 · lc medium +32 · verified · 29.3% accepted · 589 likes · top 7%

Description

A permutation of 0-indexed array nums of distinct positive integers is special if every adjacent pair satisfies divisibility: one of them divides the other. Return the count of special permutations modulo 10⁹ + 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.

Code

1

2

3

class Solution:
    def specialPerm(self, nums: List[int]) -> int:

class Solution:
    def specialPerm(self, nums: List[int]) -> int: