Beautiful Arrangement

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:

The number at the ith position is divisible by i.
i is divisible by the number at the ith position.

Now given N, how many beautiful arrangements can you construct?

Example 1:

Input: 3

Output: 3

Explanation:
The accepted permutations are: [[1,2,3], [3,2,1], [2,1,3]].
if we take [3,2,1], the first number 3 at index i = 1, is divisible by it’s index, the second number 2 is also divisible by it’s index i = 2. For the last number 1, at index i = 3, it divides it’s index completely.

Note:

N is a positive integer and will not exceed 15.

Solution:

This problem is the combination of two sub-problems. First we have to generate all the possible permutations together-with we need to check for the divisiblity test given in the question.

Using brute force can’t help in solving this types of problems. As we have to generate every possible scenerios.

We can use Backtracking algorithm efficiently.

Algorithm:

We take first number and fix it at a particular position. Once fixed we need to check for it’s divisiblity criteria based on the given conditions. If our criteria suits for the number we move to our next number to be fixed at the next position untill we fill all the position. If any number at any position fails to fullfil the required criteria, we break the whole chain of generated by the particular number.

We take boolean array visited[i] that will check if the number is already placed or not in a particular combination. We recursively call calculate function to obtain combination moving on to the the next number.

Implementation

Java

public class Solution {
    int count = 0;
    public int countArrangement(int N) {
        boolean[] visited = new boolean[N + 1];
        calculate(N, 1, visited);
        return count;
    }
    public void calculate(int N, int pos, boolean[] visited) {
        if (pos > N)
            count++;
        for (int i = 1; i <= N; i++) {
            if (!visited[i] && (pos % i == 0 || i % pos == 0)) {
                visited[i] = true;
                calculate(N, pos + 1, visited);
                visited[i] = false;
            }
        }
    }
}

Complexity Analysis:

• Time Complexity: O(k), k refers to the number of valid permutations.

• Space Complexity: O(n).