MediumArrayDynamic ProgrammingBacktrackingBit ManipulationBitmaskUpdated Sep 2026

526. Beautiful Arrangement

Asked at Rippling, Visa

Difficulty

Medium

Time

O(n * 2^n)

Space

O(n * 2^n)

Pattern

Array

Companies

2

Problem

You are given an integer n. Think about all the ways to arrange the numbers 1 to n in positions 1 to n, using each number exactly once. Such an arrangement is called beautiful if, for every position i, at least one of these two things is true: the number sitting at position i is divisible by i, or i is divisible by that number.

Return how many beautiful arrangements exist for the given n. You do not need to list them, only count them.

A quick reminder: a is divisible by b when a % b == 0. Position 1 always works, because every number is divisible by 1.

What a beautiful arrangement looks like

perm1201Position 1 holds 1 (1|1) and position 2 holds 2 (2|2)— valid.perm2101Position 1 holds 2 (1|2) and position 2 holds 1 (2 isdivisible by 1) — also valid.
For n = 2, both [1,2] and [2,1] pass the divisibility rule at every position, so the answer is 2.

Constraints

  • ●1 <= n <= 15

Examples

Example 1
Inputn = 2
Output2
WhyThe arrangements are [1,2] and [2,1]. In [1,2], position 1 holds 1 (1 divides 1) and position 2 holds 2 (2 divides 2). In [2,1], position 1 holds 2 (1 divides 2) and position 2 holds 1 (2 is divisible by 1). Both are valid, so the answer is 2.
Example 2
Inputn = 1
Output1
WhyThere is only one arrangement, [1], and position 1 holds 1, which is divisible by 1. So the count is 1.
Example 3
Inputn = 3
Output3
WhyThe valid arrangements are [1,2,3], [2,1,3] and [3,2,1]. For example, in [3,2,1] position 1 holds 3 (1 divides 3), position 2 holds 2 (2 divides 2), and position 3 holds 1 (3 is divisible by 1). Arrangements like [1,3,2] fail at position 2, because 3 is not divisible by 2 and 2 is not divisible by 3

Asked At

2 companies
CompanyDifficulty
RipplingMediumView all Rippling questions →
VisaMediumView all Visa questions →

How to Think About It

1

Brute force: generate all n! permutations and check each for the beautiful property. That's O(n! * n) - far too slow for n up to 15.

2

Key insight: use backtracking with pruning. At each position, try all unused numbers that satisfy the divisibility condition. Skip numbers that don't divide the position and whose position doesn't divide them. This prunes most branches.

3

Bitmask optimization: represent the set of used numbers as a bitmask. This makes the state compact (2^n states) and enables memoization. dp[mask] = number of ways to fill positions using the numbers in mask.

4

Memoization approach: define dfs(pos, mask) where pos is the current position to fill and mask is which numbers are used. For each unused number that satisfies the condition, recurse. Cache results by (pos, mask).

5

Edge cases: n=1 (return 1), n=2 (return 2: [1,2] and [2,1]).

Optimal Approach

Use backtracking with bitmask memoization.

  1. Define dfs(pos, mask): number of beautiful arrangements to fill positions from pos to n, given the set of used numbers in mask.
  2. Base case: if pos > n, return 1 (all positions filled).
  3. For each number i from 1 to n:
  • If i is not in mask AND (i % pos == 0 OR pos % i == 0):
    • Set bit i in mask, recurse on pos+1.
    • Sum all valid recursive results.
  1. Memoize by (pos, mask).

Walkthrough for n=3:

  • dfs(1, 000): try 1, 2, 3.
    • dfs(2, 001): try 2 (2%2==0). dfs(3, 011): try 3 (3%3==0). dfs(4, 111) = 1. Total += 1.
    • dfs(2, 010): try 1 (2%1==0). dfs(3, 011): try 3. dfs(4, 111) = 1. Total += 1.
    • dfs(2, 100): try 1 (2%1==0). dfs(3, 101): try 2 (3%2!=0, skip). try 3 (already used). Dead. Total += 0.
    • dfs(2, 100): try 2 (2%2==0). dfs(3, 110): try 1 (3%1==0). dfs(4, 111) = 1. Total += 1.
  • Result: 3.

Time: O(n * 2^n) states, each O(n) to enumerate. Space: O(n * 2^n) for memoization.

Backtracking with a bitmask

positions123012posStart at position 1 with no numbers used yet.try at pos 1123012At position 1 every number is allowed, since 1 dividesall of them.pick a number that passes the rulemark it used in the maskmove to the next positionif stuck, undo and try anothercount 1 when all positions are filledThe recursion tries choices, backtracks on dead ends,and adds 1 for each complete arrangement.dfs(pos, mask) = sum of dfs(pos+1, mask | bit(i))only for unused i with i % pos == 0 or pos % i == 0
Fill positions left to right, only try numbers that pass the rule, and remember results by (position, used-set).
ComplexityTime O(n * 2^n)Space O(n * 2^n)There are at most n * 2^n (position, used-set) states, and each state scans up to n numbers to find valid choices; the memo table stores one entry per state.

What Trips People Up in Real Interviews

1

Trying to generate all permutations and check each one. That's O(n!) and will time out for n >= 12. Use backtracking with pruning or bitmask DP.

2

Forgetting the divisibility check goes both ways. The condition is: position i divides number OR number divides position i. You need to check both i % num == 0 and num % i == 0.

3

Using 0-indexed positions instead of 1-indexed. The problem uses 1-based indexing: position 1 through n. If you use 0-indexed, adjust the divisibility check accordingly.

4

Not memoizing the backtracking. Without memoization, the same (position, mask) state can be reached through different paths, leading to exponential recomputation. Memoization brings it to O(n * 2^n).

5

Off-by-one in the bitmask. If using bit i to represent number i, make sure bit 0 is unused (numbers start from 1) or shift by 1. Mixing up the bit representation causes wrong results.

Solution Code

O(n * 2^n) time
def countArrangement(n):
    memo = {}

    def dfs(pos, mask):
        if pos > n:
            return 1
        if (pos, mask) in memo:
            return memo[(pos, mask)]
        count = 0
        for i in range(1, n + 1):
            if not (mask & (1 << i)) and (i % pos == 0 or pos % i == 0):
                count += dfs(pos + 1, mask | (1 << i))
        memo[(pos, mask)] = count
        return count

    return dfs(1, 0)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Beautiful Arrangement problem?

Given an integer n, count the number of beautiful arrangements where placing numbers 1 to n in positions 1 to n, each number at position i is divisible by i or i is divisible by the number. This tests backtracking with bitmask optimization.

How do you solve Beautiful Arrangement?

The optimal approach runs in O(n * 2^n) time and O(n * 2^n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Beautiful Arrangement?

Beautiful Arrangement is asked at Rippling, Visa. It is a medium difficulty problem.

What are common mistakes on Beautiful Arrangement?
  • Trying to generate all permutations and check each one. That's `O(n!)` and will time out for n >= 12. Use backtracking with pruning or bitmask DP.
  • Forgetting the divisibility check goes both ways. The condition is: position i divides number OR number divides position i. You need to check both `i % num == 0` and `num % i == 0`.
  • Using 0-indexed positions instead of 1-indexed. The problem uses 1-based indexing: position 1 through n. If you use 0-indexed, adjust the divisibility check accordingly.
  • Not memoizing the backtracking. Without memoization, the same (position, mask) state can be reached through different paths, leading to exponential recomputation. Memoization brings it to `O(n * 2^n)`.
  • Off-by-one in the bitmask. If using bit i to represent number i, make sure bit 0 is unused (numbers start from 1) or shift by 1. Mixing up the bit representation causes wrong results.