Leetcode 526. Beautiful Arrangement

Problem Explanation:

The problem asks for finding the number of all possible beautiful arrangements that can be constructed from a set of integers from 1 to n. A beautiful arrangement is an array of these numbers such that either the number at i-th position is divisible by i, or i is divisible by the number at i-th position.

Let's walk through an example: If n=2, two beautiful arrangements are possible: [1,2] and [2,1]. In both arrangements, each number at i-th position is either divisible by i or i is divisible by that number.

Solution Explanation:

This problem can be solved by using a depth-first search (DFS) algorithm. DFS is a recursive algorithm for traversing or searching tree or graph data structures. In DFS, we start from a node, go as deep as possible, and then backtrack.

A memoization hashmap is used to keep track of the intermediate beautiful arrangements while constructing them to reduce duplication of computation and hence increase the efficiency.

1. The function dfs takes four parameters: n, num, filled and memo. It initializes count to 0, checks whether number num can be placed at a position i (1 <= i <= n) in the arrangement, and if so, it updates our intermediate arrangement filled and incrementally computes the total beautiful arrangements count.

2. Once a beautiful arrangement is formed, it's stored in a hashmap memo, where the key is the arrangement and the value is the count of arrangements.

3. The function dfs is recursively invoked on num+1.

Python Solution:

1
2python
3class Solution:
4    def countArrangement(self, n: int) -> int:
5        memo = {}
6        def dfs(num, filled):
7            if num == n + 1:
8                return 1
9            if filled in memo:
10                return memo[filled]
11            count = 0
12            for i in range(1, n + 1):
13                if filled[i] == 'x' and (num % i == 0 or i % num == 0):
14                    filled[i] = 'o'
15                    count += dfs(num + 1, filled)
16                    filled[i] = 'x'
17            memo[filled] = count
18            return count
19        return dfs(1, ['x'] * (n + 1))

In the Python solution, we use a list filled to test and keep track of each number's position in the array.

Java Solution:

1
2java
3class Solution {
4    int[] memo;
5    public int countArrangement(int n) {
6        memo = new int[1 << n];
7        return dfs(n, 1, 0);
8    }
9    private int dfs(int n, int pos, int mask) {
10        if (pos > n) return 1;
11        if (memo[mask] != 0) return memo[mask];
12        int res = 0;
13        for (int i = 1; i <= n; i++) {
14            if ((mask & (1 << (i - 1))) == 0 && (pos % i == 0 || i % pos == 0)) {
15                res += dfs(n, pos + 1, mask | (1 << (i - 1)));
16            }
17        }
18        memo[mask] = res;
19        return res;
20    }
21}

Java solution also applies the same concept but uses a bitmask to keep track of the state of each number.

JavaScript Solution:

1
2javascript
3var countArrangement = function(N) {
4    let count = 0;
5    const visited = new Array(N+1).fill(false);
6    dfs(1);
7    return count;
8    
9    function dfs(idx){
10        if(idx > N)
11            count++;
12        
13        for(let i=1; i<=N; i++){
14            if(!visited[i] && (idx % i == 0 || i % idx == 0)){
15                visited[i] = true;
16                dfs(idx+1);
17                visited[i] = false;
18            }
19        }  
20    }
21};

JavaScript solution uses a recursive helper function dfs(idx) to try each number at each index and a variable visited to track whether a number is used or not.

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int countArrangement(int N) {
6        int memo[1<<15] = {0};
7        return dfs(1, N, 0, &memo[0]);
8    }
9
10    int dfs(int i, int N, int used, int* memo) {
11        if (i > N) return 1;
12        if (memo[used] != 0) return memo[used];
13        int total = 0;
14        for (int j = 1; j <= N; ++j) {
15            if (!(used & (1 << (j - 1))) && (i%j == 0 || j%i == 0))
16                total += dfs(i + 1, N, used | (1 << (j - 1)), memo);
17        }
18        return memo[used] = total;
19    }
20};

In C++, we employ array memo to maintain state of the arrangement.

C# Solution:

1
2c#
3public class Solution {
4    Dictionary<int, int> memo = new Dictionary<int, int>();
5    public int CountArrangement(int n) {
6        return dfs(n, 0);
7    }
8    int dfs(int n, int used) {
9        if (used == (1 << n) - 1) return 1;
10        if (memo.ContainsKey(used)) return memo[used];
11        int res = 0;
12        for (int i = 1; i <= n; i++) 
13            if((used & (1 << (i - 1))) == 0 && (((used >> 1) + 1) % i == 0 || i % ((used >> 1) + 1) == 0))
14                res += dfs(n, used | (1 << (i - 1)));
15        memo[used] = res;
16        return res;
17    }
18}

The C# solution is similar to the other solutions, using a dictionary memo for memoization and a used mask to track state.Ruby Solution:

1
2ruby
3def count_arrangement(n)
4    return dfs(n, 0, Array.new(n+1, false))
5end
6
7def dfs(n, pos, used)
8    return 1 if pos == n
9    return 0 if used[pos]
10    res = 0
11    for i in 1..n
12        next if used[i] or pos%i != 0 and i%pos != 0
13        used[i] = true
14        res += dfs(n, pos+1, used)
15        used[i] = false
16    end
17    return res
18end

In the Ruby solution, we use an array used to track the state of each number and a helper function dfs. In this function, we iterate through 1..n, if the current number i is not used and either i is divisible by pos or pos is divisible by i, we use i, and recursively call dfs on pos+1.

Rust Solution:

1
2rust
3use std::collections::HashMap;
4
5impl Solution {
6    fn count(n: i32, pos: usize, visited: i32, memo: &mut HashMap<i32, i32>) -> i32 {
7        if pos == n as usize {
8            return 1;
9        }
10        if let Some(&count) = memo.get(&visited) {
11            return count;
12        }
13        let mut count = 0;
14        for i in 0..n {
15            if visited & (1 << i) != 0 {
16                continue;
17            }
18            if (pos + 1) % (i + 1) != 0 && (i + 1) % (pos + 1) != 0 {
19                continue;
20            }
21            count += Self::count(n, pos + 1, visited | (1 << i), memo);
22        }
23        memo.insert(visited, count);
24        count
25    }
26
27    pub fn count_arrangement(n: i32) -> i32 {
28        Self::count(n, 0, 0, &mut HashMap::new())
29    }
30}

Notably, the Rust solution also follows a similar approach as the other solutions but it has a HashMap memo for memoization and uses bitwise operations to track the state of each number, i.e., whether it has been used or not.

In all these solutions, the time complexity of the algorithm is approximately O(n!) due to the fact that in the worst case, it might have to try out all the permutations of the numbers from 1 to n. The space complexity is O(n) for the recursion stack and memoization data structures.