1330. Beautiful Arrangement — Bitmask Backtracking

Given n distinct positive integers, count the permutations that place them into positions 1 through n such that at every position i the placed value v satisfies v % i == 0 or i % v == 0. The classic Beautiful Arrangement problem is the special case where the values are exactly 1..n.

Input: A JSON object {"nums": [<distinct positive integers>]}.

Output: Return the number of valid arrangements.

Examples

Input: {"nums":[1,2]}
Output: 2
Explanation: Both orderings satisfy the divisibility rule -> 2.

Input: {"nums":[1,2,3]}
Output: 3
Explanation: The classic n=3 answer is 3.

Constraints

• 1 <= len(nums) <= 14
• 1 <= nums[i] <= 50
• values are distinct

Asked by