Last updated on July 18th, 2024 at 02:57 am

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

Topics

Backtracking

Companies

Google

Level of Question

Medium

Beautiful Arrangement 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

1. Beautiful Arrangement Solution C++

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);
    }
};

2. Beautiful Arrangement Solution Java

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;
            }
        }
    }
}

3. Beautiful Arrangement Solution JavaScript

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;
}

4. Beautiful Arrangement Solution Python

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