##### Welcome to Subscribe On Youtube
• /**

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.
Note:
N is a positive integer and will not exceed 15.

*/

public class Beautiful_Arrangement {

public class Solution_trim {
int count = 0;
public int countArrangement(int N) {
int[] nums = new int[N];
for (int i = 1; i <= N; i++)
nums[i - 1] = i;
permute(nums, 0);
return count;
}
public void permute(int[] nums, int l) {
if (l == nums.length) {
count++;
}
for (int i = l; i < nums.length; i++) {
swap(nums, i, l);

// @note: only the current index is ok, then add it
if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
permute(nums, l + 1);
}
swap(nums, i, l);
}
}
public void swap(int[] nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
}

public class Solution {
int count = 0;
public int countArrangement(int N) {

if (N < 0) {
return count;
}

int[] nums = new int[N];
for (int i = 1; i <= N; i++) {
nums[i - 1] = i;
}

permute(nums, 0);

return count;
}

public void permute(int[] nums, int l) {
if (l == nums.length - 1) {
isBeautiful(nums);
}

for (int i = l; i < nums.length; i++) {
swap(nums, i, l);
permute(nums, l + 1);
swap(nums, i, l);
}
}

public void swap(int[] nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}

private void isBeautiful (int[] nums) {
int i;
for (i = 1; i <= nums.length; i++) {
if (nums[i - 1] % i != 0 && i % nums[i - 1] != 0)
break;
}
if (i == nums.length + 1) {
count++;
}
}
}

}

############

class Solution {
public int countArrangement(int N) {
int maxn = 1 << N;
int[] f = new int[maxn];
f[0] = 1;
for (int i = 0; i < maxn; ++i) {
int s = 1;
for (int j = 0; j < N; ++j) {
s += (i >> j) & 1;
}
for (int j = 1; j <= N; ++j) {
if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) {
f[i | (1 << (j - 1))] += f[i];
}
}
}
return f[maxn - 1];
}
}


• // OJ: https://leetcode.com/problems/beautiful-arrangement/
// Time: O(K) where K is the number of valid permuataions
// Space: O(N)
class Solution {
int dfs(vector<int> &v, int start) {
if (start == v.size()) return 1;
int ans = 0;
for (int i = start; i < v.size(); ++i) {
if (v[i] % (start + 1) && (start + 1) % v[i]) continue;
swap(v[i], v[start]);
ans += dfs(v, start + 1);
swap(v[i], v[start]);
}
return ans;
}
public:
int countArrangement(int n) {
vector<int> v(n);
iota(begin(v), end(v), 1);
return dfs(v, 0);
}
};

• class Solution:
def countArrangement(self, n: int) -> int:
def dfs(i):
nonlocal ans, n
if i == n + 1:
ans += 1
return
for j in match[i]:
if not vis[j]:
vis[j] = True
dfs(i + 1)
vis[j] = False

ans = 0
vis = [False] * (n + 1)
match = defaultdict(list)
for i in range(1, n + 1):
for j in range(1, n + 1):
if j % i == 0 or i % j == 0:
match[i].append(j)

dfs(1)
return ans

############

class Solution(object):
def countArrangement(self, N):
"""
:type N: int
:rtype: int
"""

def dfs(pos, unused):
if len(unused) == 0:
return 1
ret = 0
for num in list(unused):
if pos % num == 0 or num % pos == 0:
unused -= {num}
ret += dfs(pos + 1, unused)
unused |= {num}
return ret

return dfs(1, set([i for i in range(1, N + 1)]))


• func countArrangement(n int) int {
ans := 0
match := make(map[int][]int)
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
if i%j == 0 || j%i == 0 {
match[i] = append(match[i], j)
}
}
}
vis := make([]bool, n+1)

var dfs func(i int)
dfs = func(i int) {
if i == n+1 {
ans++
return
}
for _, j := range match[i] {
if !vis[j] {
vis[j] = true
dfs(i + 1)
vis[j] = false
}
}
}

dfs(1)
return ans
}

• function countArrangement(n: number): number {
const vis = new Array(n + 1).fill(0);
const match = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
if (i % j === 0 || j % i === 0) {
match[i].push(j);
}
}
}

let res = 0;
const dfs = (i: number, n: number) => {
if (i === n + 1) {
res++;
return;
}
for (const j of match[i]) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, n);
vis[j] = false;
}
}
};
dfs(1, n);
return res;
}


• impl Solution {
fn dfs(i: usize, n: usize, mat: &Vec<Vec<usize>>, vis: &mut Vec<bool>, res: &mut i32) {
if i == n + 1 {
*res += 1;
return;
}
for &j in mat[i].iter() {
if !vis[j] {
vis[j] = true;
Self::dfs(i + 1, n, mat, vis, res);
vis[j] = false;
}
}
}

pub fn count_arrangement(n: i32) -> i32 {
let n = n as usize;
let mut vis = vec![false; n + 1];
let mut mat = vec![Vec::new(); n + 1];
for i in 1..=n {
for j in 1..=n {
if i % j == 0 || j % i == 0 {
mat[i].push(j);
}
}
}

let mut res = 0;
Self::dfs(1, n, &mat, &mut vis, &mut res);
res
}
}


• class Solution {
int count = 0;

public int countArrangement(int N) {
if (N == 0)
return 0;
boolean[] used = new boolean[N + 1];
backtrack(N, 1, used);
return count;
}

public void backtrack(int N, int position, boolean[] used) {
if (position > N)
count++;
else {
for (int i = 1; i <= N; i++) {
if (!used[i] && (i % position == 0 || position % i == 0)) {
used[i] = true;
backtrack(N, position + 1, used);
used[i] = false;
}
}
}
}
}

############

class Solution {
public int countArrangement(int N) {
int maxn = 1 << N;
int[] f = new int[maxn];
f[0] = 1;
for (int i = 0; i < maxn; ++i) {
int s = 1;
for (int j = 0; j < N; ++j) {
s += (i >> j) & 1;
}
for (int j = 1; j <= N; ++j) {
if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) {
f[i | (1 << (j - 1))] += f[i];
}
}
}
return f[maxn - 1];
}
}


• // OJ: https://leetcode.com/problems/beautiful-arrangement/
// Time: O(K) where K is the number of valid permuataions
// Space: O(N)
class Solution {
int dfs(vector<int> &v, int start) {
if (start == v.size()) return 1;
int ans = 0;
for (int i = start; i < v.size(); ++i) {
if (v[i] % (start + 1) && (start + 1) % v[i]) continue;
swap(v[i], v[start]);
ans += dfs(v, start + 1);
swap(v[i], v[start]);
}
return ans;
}
public:
int countArrangement(int n) {
vector<int> v(n);
iota(begin(v), end(v), 1);
return dfs(v, 0);
}
};

• class Solution:
def countArrangement(self, n: int) -> int:
def dfs(i):
nonlocal ans, n
if i == n + 1:
ans += 1
return
for j in match[i]:
if not vis[j]:
vis[j] = True
dfs(i + 1)
vis[j] = False

ans = 0
vis = [False] * (n + 1)
match = defaultdict(list)
for i in range(1, n + 1):
for j in range(1, n + 1):
if j % i == 0 or i % j == 0:
match[i].append(j)

dfs(1)
return ans

############

class Solution(object):
def countArrangement(self, N):
"""
:type N: int
:rtype: int
"""

def dfs(pos, unused):
if len(unused) == 0:
return 1
ret = 0
for num in list(unused):
if pos % num == 0 or num % pos == 0:
unused -= {num}
ret += dfs(pos + 1, unused)
unused |= {num}
return ret

return dfs(1, set([i for i in range(1, N + 1)]))


• func countArrangement(n int) int {
ans := 0
match := make(map[int][]int)
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
if i%j == 0 || j%i == 0 {
match[i] = append(match[i], j)
}
}
}
vis := make([]bool, n+1)

var dfs func(i int)
dfs = func(i int) {
if i == n+1 {
ans++
return
}
for _, j := range match[i] {
if !vis[j] {
vis[j] = true
dfs(i + 1)
vis[j] = false
}
}
}

dfs(1)
return ans
}

• function countArrangement(n: number): number {
const vis = new Array(n + 1).fill(0);
const match = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
if (i % j === 0 || j % i === 0) {
match[i].push(j);
}
}
}

let res = 0;
const dfs = (i: number, n: number) => {
if (i === n + 1) {
res++;
return;
}
for (const j of match[i]) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, n);
vis[j] = false;
}
}
};
dfs(1, n);
return res;
}


• impl Solution {
fn dfs(i: usize, n: usize, mat: &Vec<Vec<usize>>, vis: &mut Vec<bool>, res: &mut i32) {
if i == n + 1 {
*res += 1;
return;
}
for &j in mat[i].iter() {
if !vis[j] {
vis[j] = true;
Self::dfs(i + 1, n, mat, vis, res);
vis[j] = false;
}
}
}

pub fn count_arrangement(n: i32) -> i32 {
let n = n as usize;
let mut vis = vec![false; n + 1];
let mut mat = vec![Vec::new(); n + 1];
for i in 1..=n {
for j in 1..=n {
if i % j == 0 || j % i == 0 {
mat[i].push(j);
}
}
}

let mut res = 0;
Self::dfs(1, n, &mat, &mut vis, &mut res);
res
}
}