Last Updated: 13 Mar, 2021

Arrangement

Moderate

Asked in companies

Problem statement

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.

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

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

1 <= T <= 10
0 <= N <= 15

Time Limit: 1 sec

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.

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.