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.
-
The function
dfs
takes four parameters: n, num, filled and memo. It initializes count to 0, checks whether numbernum
can be placed at a positioni
(1 <= i <= n) in the arrangement, and if so, it updates our intermediate arrangementfilled
and incrementally computes the total beautiful arrangementscount
. -
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. -
The function
dfs
is recursively invoked onnum+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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.