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: 2 Output: 2 Explanation:

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1). Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2). The second beautiful arrangement is [2, 1]: Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1). Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

Solution: Backtracking

The idea behind this approach is simple. We try to create all the permutations of numbers from 1 to N. We can fix one number at a particular position and check for the divisibility criteria of that number at the particular position.

But, we need to keep a track of the numbers which have already been considered earlier so that they aren't reconsidered while generating the permutations.

If the current number doesn't satisfy the divisibility criteria, we can leave all the permutations that can be generated with that number at the particular position. This helps to prune the search space of the permutations to a great extent. We do so by trying to place each of the numbers at each position.

int countArrangement(int N) {
    vector<bool> visited;
    for (int i=0; i<=N; ++i) visited.push_back(false);

    int count = 0;
    counts(N, 1, &count, visited);
    return count;
}

void counts(int n, int pos, int *count, vector<bool>& vs) {
    // This means that all positions satisfy the required condition, thus we found an answer.
    if (pos > n) *count += 1; 

    for (int i=1; i<=n; ++i) {
        if (!vs[i] && (pos % i == 0 || i % pos == 0)) {
            vs[i] = true;
            counts(n, pos+1, count, vs);
            vs[i] = false;
        }
    }
}

Solution: By Swapping elements

int countArrangement(int N) {
    vector<int> visited;
    for (int i=0; i<N; ++i) visited.push_back(i+1);
    return counts(N, visited);
}

int counts(int n, vector<int>& vs) {
    if (n <= 0) return 1;
    int ans = 0;
    for (int i=0; i<n; ++i) {
        if (vs[i]%n==0 || n%vs[i]==0) {
            swap(vs[i], vs[n-1]);
            ans += counts(n-1, vs);
            swap(vs[i], vs[n-1]);
        }
    }
    return ans;
}

results matching ""

    No results matching ""