Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Last Updated: 13 Mar, 2021


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

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.


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


01 Approach

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