Arrangement
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

Question

Arrangement

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

Accepted Answer

All possible permutations

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.

Space Complexity: O(n)Explanation:

O(N), where 'N' is the length of the array.

We only need to create an array of the size N.

Time Complexity: O(n!)Explanation:

O(N! * N), where ‘N’ is the length of the array.

There are ‘N!' Permutations and for each permutation, we have to check its divisibility in O(N)

Therefore time complexity is O(N! * N).

Accepted Answer

Backtracking approach

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.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the given array.

We create a new string and calling ‘UTIL’ recursively also needed to store in the call stack which is O(N) therefore, extra space of order of ‘N’ is needed.

Time Complexity: OtherExplanation:

O(K), where ‘K’ is the number of valid permutations.

We need to iterate over the sting and create a new one. Therefore the time complexity is in order of ‘N’.

Python (3.5)

'''

    Time complexity: O(K)

    Space complexity: O(N)



    where 'K' is the valid number of permutaion

    and 'N' is the number of elementes in array.

'''



def util(val, vis, n, res):



    if (val > n):

        res[0] += 1

        return



    for i in range(1, n + 1):

        if (vis[i] == False and (i % val == 0 or val % i == 0)):

            # If i have not used i before then i will will use it.

            vis[i] = True



            util(val + 1, vis, n, res)

            vis[i] = False





def countArrangment(n):



    res = [0]

    vis = [False] * (n + 1)



    util(1, vis, n, res)



    return res[0]

Java (SE 1.8)

/*
    Time complexity: O(K)
    Space complexity: O(N)

    where 'K' is the valid number of permutaion
    and 'N' is the number of elementes in array.
*/

public class Solution {
    public static int res = 0;

    public static void util(int val, boolean[] vis, int n) {
        if (val > n) {
            res++;
            return;
        }

        for (int i = 1; i <= n; i++) {
            if ( !vis[i] && (i % val == 0 || val % i == 0) ) {
                // If we have not used 'i' before then we will will use it.
                vis[i] = true;

                util(val + 1, vis, n);
                vis[i] = false;
            }
        }
    }

    public static int countArrangement(int n) {
        res = 0;
        boolean[] vis = new boolean[n + 1];  
        
        util(1, vis, n);
        
        return res;
    }
}

C++ (g++ 5.4)

/*
    Time complexity: O(K)
    Space complexity: O(N)

    where 'K' is the valid number of permutaion
    and 'N' is the number of elementes in array.
*/

int res = 0;

void util(int val, vector &vis, int n) {
    if (val > n) {
        res++;
        return;
    }

    for (int i = 1; i <= n; i++) {
        if ( !vis[i] && (i % val == 0 || val % i == 0) ) {
            // If we have not used 'i' before then we will will use it.
            vis[i] = true;

            util(val + 1, vis, n);
            vis[i] = false;
        }
    }
}

int countArrangement(int n) {
    res = 0;
    // Nothing is placed initially.
    vector vis(n + 1, false);  
    
    util(1, vis, n);
    
    return res;
}