# Arrangement

Posted: 13 Mar, 2021

Difficulty: Moderate

#### You are given a number 'N'. Your goal is to find the number of permutations of the list 'A' = [1, 2, ......, N], satisfying either of the following conditions:

#### A[i] is divisible by i or i is divisible by A[i], for every 'i' from 1 to 'N'.

##### Input Format:

```
The first line of the input contains ‘T’ denoting the number of test cases.
The first line of each test case contains an integer N.
```

##### Output Format:

```
For each test case return the number of satisfying permutations in a new line.
```

#### Note:

```
You do not need to print anything or take input. This already has been taken care of. Just implement the function.
```

##### Constraints:

```
1 <= T <= 10
0 <= N <= 15
Time Limit: 1 sec
```

Approach 1

- In the brute force method, we can find out all the arrays that can be formed using the numbers from 1 to ‘N’(all permutations).
- Then, we iterate over all the elements of every permutation generated and check for the required conditions of divisibility i.e. for every index ‘i’ from 1 to ‘N’, either of the following condition should satisfy A[i]%i=0 or i%A[i]=0.
- If the permutation satisfies the divisibility condition we increment our answer by 1.

Approach 2

The idea behind this approach is to construct permutations recursively while satisfying the divisibility criteria for each index as we build it.

We create a boolean array so that we can keep track of what’s already in the array.

We use backtracking to maintain this boolean array.

Algorithm:

- We make a boolean array ( VISITED ) of size ‘N’, here VISITED[i] is true if value i is already placed in the array till now.
- Then we make a recursive function, CALCULATE(N, POS, VISITED), where ‘POS’ is the current position in the array.
- For every value of ‘POS’ from 1 to ‘N’, we put all values from 1 to ‘N’, not in the ‘VISITED’ array which also satisfies the divisibility condition in the current position. Then we move to the next position to recursively calculate the answer. After setting ‘VISITED’ as true for the value.
- Then we calculate the answer recursively.
- After the end of recursion, we set ‘VISITED’ as false for the value. As we might use the value in the future indexes.

SIMILAR PROBLEMS

# Combinations

Posted: 21 Dec, 2021

Difficulty: Moderate

# Unique Paths III

Posted: 27 Dec, 2021

Difficulty: Hard

# Ninja And The Clan

Posted: 17 Apr, 2022

Difficulty: Moderate

# Combination Sum III

Posted: 25 May, 2022

Difficulty: Moderate

# Generate All Strings

Posted: 9 Jul, 2022

Difficulty: Moderate