# Beautiful Arrangement LeetCode Solution

Here, We see Beautiful Arrangement LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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:
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:
Input: n = 1
Output: 1

## Beautiful Arrangement SolutionC++

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);
}
};Code language: PHP (php)

## Beautiful Arrangement SolutionJava

class Solution {
int noOfBeautifulArrangement= 0;
public int countArrangement(int n) {
boolean []visited= new boolean[n+1];
permutationGenerator(n, visited, 1, "");
return noOfBeautifulArrangement;
}
public void permutationGenerator(int n, boolean []visited, int c, String sequenceSoFar){
if( c > n) {
noOfBeautifulArrangement+= 1;
System.out.println(sequenceSoFar.substring(1)+".\n\n");
return;
}
for ( int i= 1; i <= n; i++){
if ( !visited[i] && ( i % c == 0 || c % i == 0 )){
visited[i]= true;
permutationGenerator( n, visited, c+1, sequenceSoFar+","+i);
visited[i]= false;
}
}
}
}Code language: JavaScript (javascript)

## Beautiful Arrangement SolutionJavaScript

var countArrangement = function(n) {
let count = 0;
const nums = [];
for(let i = 1; i <= n; i++) {
nums.push(i);
}
function findArrangements(index) {
if (index == nums.length) {
count++;
}
for(let i = index; i < nums.length; i++) {
swap(nums, i, index);
if ((index + 1) % nums[index] === 0 ||
nums[index] % (index + 1) === 0) {
findArrangements(index + 1);
}
swap(nums, i, index);
}
}
findArrangements(0);
return count;
};
function swap(nums, one, two) {
let temp = nums[one];
nums[one] = nums[two];
nums[two] = temp;
}Code language: JavaScript (javascript)

## Beautiful Arrangement SolutionPython

class Solution(object):
def countArrangement(self, n):
self.res = 0
nums = [i for i in range(1, n+1)]
def dfs(nums, i = 1):
if i == n+1:
self.res += 1
return
for j, num in enumerate(nums):
if not(num % i and i % num):
dfs(nums[:j] + nums[j+1:], i+1)
dfs(nums)
return self.res
Scroll to Top