Arrangement

Moderate

0/80

Average time to solve is 15m

Contributed by

5 upvotes

Asked in companies

Problem statement

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'.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
1
2

Sample Output 1:

1
2

Explanation for Sample Input 1:

In test case 1:
The only permutation is A=[1]
    A[1] = 1 is divisible by i = 1

The permutation is satisfying the conditions therefore answer is 1

In test case 2:
The 1st permutation is A=[1,2]:
    A[1] = 1 is divisible by i = 1
    A[2] = 2 is divisible by i = 2
The 2nd permutation is A=[2,1]:
    A[1] = 2 is divisible by i = 1
    i = 2 is divisible by A[2] = 1

Both permutations are satisfying either of the conditions therefore answer is 2

Sample Input 2:

2
3
4

Sample Output 2:

3
8

Hint 1

Hint 2

Generate all possible permutations

Approaches (2)

Approach 1

Approach 2

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.

Time Complexity

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).

Space Complexity

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

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

(100% EXP penalty)

Arrangement

Console