Count Permutations with Position Divisibility
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Count permutations of the integers 1 through n such that at every one-based position i, either the value at i divides i or i divides that value. Each integer is used exactly once.
```cpp
class Solution {
public:
int countArrangement(int n);
};
```
### Examples
**Example 1:**
```text
n = 3
Output: 3
Explanation: [1,2,3], [2,1,3], and [3,2,1] qualify.
```
**Example 2:**
```text
n = 4
Output: 8
Explanation: Position 3 can hold only 1 or 3. If it holds 1, position 1 must hold 3 and values 2 and 4 can swap between positions 2 and 4, giving 2 arrangements. If it holds 3, all 6 permutations of values 1, 2 and 4 work in the remaining positions. Thus 2+6=8.
```
### Constraints
- The permutation size n is an integer in 1..15.
### Clarifying Questions
Use one-based positions and count arrangements rather than returning an arbitrary example.
```hint Read the boundary condition
Once the used values are known, is the next position also known?
```
### Contract considerations
Use one-based positions and count arrangements rather than returning an arbitrary example.