Is Beautiful Arrangement easy or hard?

Beautiful Arrangement is classified as a medium difficulty problem. The core idea—checking divisibility while building permutations—is straightforward, but recognizing pruning opportunities or implementing the bitmask DP optimization requires stronger algorithmic thinking.

How to solve Beautiful Arrangement in O(n * 2^n)?

Use dynamic programming with bitmasking. Represent which numbers are used with a bitmask and let the number of set bits determine the current position. For each mask, try adding an unused number that satisfies the divisibility condition. Memoizing results for every mask ensures each state is computed once, giving O(n * 2^n) time complexity.

What is the best approach for Beautiful Arrangement?

Backtracking with pruning is the most common approach. It builds the permutation position by position and only places numbers that satisfy the divisibility rule with the current index. Because many permutations are rejected early, the practical runtime is much faster than generating all n! permutations. For n ≤ 15, this approach performs well and is easy to explain in interviews.

What data structure is used in Beautiful Arrangement?

Typical implementations use a boolean array or bitmask to track which numbers are already placed in the permutation. The optimized solution uses a bitmask integer combined with dynamic programming to represent subsets of chosen numbers efficiently.

What is the time complexity of Beautiful Arrangement?

The backtracking solution has worst‑case time complexity O(n!) because it explores permutations, but pruning significantly reduces the search space. The optimized dynamic programming solution using bitmasking runs in O(n * 2^n) time with O(2^n) space by storing results for each subset of numbers.

Beautiful Arrangement Python or Java solution approach?

In Python or Java, the standard solution uses recursion with backtracking. Maintain a visited array or bitmask, try placing each unused number at position i, and check the divisibility condition before recursing. The alternative implementation uses a DP array indexed by bitmask to count arrangements.

Is Beautiful Arrangement asked at Google, Amazon, or Meta?

Beautiful Arrangement appears frequently in coding interview preparation sets and has been reported in interviews at companies like Amazon and Google. The problem tests recursion, pruning strategies, and bitmask dynamic programming, which are common patterns in technical interviews.

Description Solution Video 16:18

526. Beautiful Arrangement

Medium64.9% acceptance6 companies

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: