Last updated on February 2nd, 2025 at 04:40 am

Here, we see a Beautiful Arrangement LeetCode Solutions. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Backtracking

Companies

Google

Level of Question

Medium

Beautiful Arrangement LeetCode Solution

1. 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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Backtracking”. Backtracking is a general algorithmic technique that involves exploring all possible configurations of a problem and “backtracking” when a configuration is invalid or does not lead to a solution.

3. Code Implementation in Different Languages

3.1 Beautiful Arrangement 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);
    }
};

3.2 Beautiful Arrangement 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.3 Beautiful Arrangement 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;
}

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

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n!)	O(n)
Java	O(n!)	O(n)
JavaScript	O(n!)	O(n)
Python	O(n!)	O(n)

1. Time Complexity:
   • The time complexity is O(n!) because the algorithm generates all permutations of the numbers from 1 to n.
   • For each permutation, it checks the “beautiful arrangement” condition, which is O(1) for each position.
2. Space Complexity:
   • The space complexity is O(n) due to the recursion stack, which can go up to a depth of n.