Beautiful Arrangement Problem


Description

LeetCode Problem 526.

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

  • perm[i] is divisible by i.
  • i is divisible by perm[i].

Given an integer n, return the number of the beautiful arrangements that you can construct.

Example 1:

1
2
3
4
5
6
7
8
9
Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
- perm[1] = 1 is divisible by i = 1
- perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm[1] = 2 is divisible by i = 1
- i = 2 is divisible by perm[2] = 1

Example 2:

1
2
Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 15


Sample C++ Code using Backtracking

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




Related Posts

24 Game Problem

LeetCode 679. You are given an integer array cards of...

Matchsticks To Square Problem

LeetCode 473. You are given an integer array matchsticks where...

Increasing Subsequences Problem

LeetCode 491. Given an integer array nums, return all the...

Binary Watch Problem

LeetCode 401. A binary watch has 4 LEDs on the...

Beautiful Arrangement Problem

LeetCode 526. Suppose you have n integers labeled 1 through...

Remove Invalid Parentheses Problem

LeetCode 301. Given a string s that contains parentheses and...