Special Permutations
01 · Problem
You are given an array nums of n distinct positive integers. A permutation of nums is special if for every adjacent pair of positions i and i + 1, one of the two values divides the other, that is nums[i] % nums[i + 1] == 0 or nums[i + 1] % nums[i] == 0.
Return the number of special permutations of nums, modulo 10^9 + 7.
02 · Examples
nums = [1,2,3]
2
1 divides everything, but 2 and 3 do not divide each other, so they cannot be adjacent. The valid orders are [2,1,3] and [3,1,2].
nums = [2,4,8]
6
Every pair has one value dividing the other, so all 3! = 6 permutations are special.
nums = [3,5,7]
0
No pair of these values divides each other, so no permutation can be special.
03 · Constraints
- 012 <= nums.length <= 14
- 021 <= nums[i] <= 109
- 03All values in nums are distinct
04 · Optimal complexity
- Time
- O(2^n * n^2)
- Space
- O(2^n * n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.