Beautiful Arrangement

MEDIUM

Description

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

Constraints:

1 <= n <= 15

Approaches

Checkout 3 different approaches to solve Beautiful Arrangement. Click on different approaches to view the approach and algorithm in detail.

Brute Force by Generating All Permutations

The most straightforward way to solve this problem is to generate every possible arrangement of numbers from 1 to n and then check if each arrangement is "beautiful". We can maintain a counter that gets incremented for every beautiful arrangement found.

Algorithm

Create an array nums containing numbers from 1 to n.
Define a recursive function, say permute(nums, start), which generates all permutations of the subarray starting at start.
The base case for the recursion is when start reaches the end of the array. This signifies that a full permutation has been formed.
In the base case, we call a helper function isBeautiful(nums) to check if the generated permutation satisfies the condition for all indices i from 1 to n.
If the permutation is beautiful, we increment a global counter.
The recursive step involves iterating from the start index to the end, swapping the element at start with the current element, making a recursive call for the next position (start + 1), and then swapping back to backtrack and explore other possibilities.

We can implement this using a recursive function that generates all permutations of the numbers.

class Solution {
    int count = 0;
    public int countArrangement(int n) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        permute(nums, 0);
        return count;
    }

    private void permute(int[] nums, int start) {
        if (start == nums.length) {
            if (isBeautiful(nums)) {
                count++;
            }
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1);
            swap(nums, start, i); // backtrack
        }
    }

    private boolean isBeautiful(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // Problem is 1-indexed, so we check nums[i] against position i+1
            if (nums[i] % (i + 1) != 0 && (i + 1) % nums[i] != 0) {
                return false;
            }
        }
        return true;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Complexity Analysis

Time Complexity: O(n! * n). There are `n!` possible permutations. For each permutation, we iterate through all `n` elements to check if it's a beautiful arrangement.Space Complexity: O(n). The recursion depth can go up to `n`.

Pros and Cons

Pros:

Conceptually simple and easy to implement.

Cons:

Extremely inefficient. The factorial growth makes it infeasible for n larger than 10 or 11.

Code Solutions

Checking out 3 solutions in different languages for Beautiful Arrangement. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Beautiful Arrangement

Patterns:

Dynamic ProgrammingBacktrackingBit ManipulationBitmask

Data Structures:

Array

Companies:

Cisco |Salesforce |HashedIn |UBS |