Beautiful Arrangement

🎯

Beautiful Arrangement

mediumBACKTRACKINGAmazonGoogle

Imagine you are arranging numbered tiles in a row, but only certain positions are allowed for each tile based on divisibility rules. How many beautiful arrangements can you create?

💡 This problem is a classic backtracking challenge where you generate permutations with constraints. Beginners often struggle because they try to generate all permutations blindly without pruning, leading to inefficiency and confusion about how to apply constraints during recursion.

📋

Problem Statement

Given an integer n, count the number of the beautiful arrangements that you can construct. A beautiful arrangement is defined as an array of the numbers from 1 to n such that for every position i (1-indexed), either the number at position i is divisible by i or i is divisible by the number.

1 ≤ n ≤ 15

💡

Example

Input"n = 2"

Output2

The two beautiful arrangements are [1,2] and [2,1]. For position 1, 1 divides 1 and 2 divides 1 (false), but 1 divides 2 (true). For position 2, 2 divides 2 and 1 divides 2.

• n = 1 → output: 1 (only one number, trivially beautiful)
• n = 0 → output: 0 (no numbers, no arrangements)
• n = 15 → output: large number, tests efficiency
• n = 3 → output: 3 (small input with multiple valid permutations)

⚠️

Common Mistakes

Not pruning early and generating all permutations

Code runs too slowly and times out on larger inputs

✅ Add divisibility checks before recursing deeper to prune invalid branches

Incorrect indexing (0-based vs 1-based) when checking divisibility

Incorrect count or wrong results

✅ Remember positions are 1-indexed; adjust indices accordingly

Not backtracking used state properly (forgetting to unmark used numbers)

Misses valid permutations or counts duplicates

✅ Always unmark used numbers after recursive calls

Using bitmask incorrectly (off-by-one bit shifts)

Numbers appear used or unused incorrectly, leading to wrong counts

✅ Use 1 << (num - 1) with num starting from 1, or adjust indexing consistently

🧠

Brute Force (Generate All Permutations and Check)

💡 This approach exists to build foundational understanding by enumerating all permutations and checking the condition. It is straightforward but inefficient, helping beginners grasp the problem's constraints and the need for pruning.

Intuition

Generate every permutation of numbers 1 to n, then check if each permutation satisfies the divisibility condition at every position.

Algorithm

1. Generate all permutations of numbers from 1 to n.
2. For each permutation, check if for every position i, the number at position i divides i or i divides the number.
3. Count the permutations that satisfy the condition.
4. Return the count.

💡 This algorithm is conceptually simple but computationally expensive because it does not prune invalid permutations early.

</>

Code

from itertools import permutations

def countArrangement(n: int) -> int:
    count = 0
    for perm in permutations(range(1, n+1)):
        if all((perm[i] % (i+1) == 0) or ((i+1) % perm[i] == 0) for i in range(n)):
            count += 1
    return count

# Driver code
if __name__ == '__main__':
    print(countArrangement(2))  # Output: 2

Line Notes

from itertools import permutationsImport permutations to generate all possible orderings of numbers

for perm in permutations(range(1, n+1))Iterate over every possible permutation of numbers 1 to n

all((perm[i] % (i+1) == 0) or ((i+1) % perm[i] == 0) for i in range(n))Check the divisibility condition for every position in the permutation

count += 1Increment count if the current permutation is a beautiful arrangement

import java.util.*;

public class BeautifulArrangement {
    public static int countArrangement(int n) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) nums.add(i);
        return permute(nums, 0);
    }

    private static int permute(List<Integer> nums, int start) {
        if (start == nums.size()) {
            for (int i = 0; i < nums.size(); i++) {
                int pos = i + 1;
                int val = nums.get(i);
                if (val % pos != 0 && pos % val != 0) return 0;
            }
            return 1;
        }
        int count = 0;
        for (int i = start; i < nums.size(); i++) {
            Collections.swap(nums, i, start);
            count += permute(nums, start + 1);
            Collections.swap(nums, i, start);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countArrangement(2)); // Output: 2
    }
}

Line Notes

for (int i = 1; i <= n; i++) nums.add(i);Initialize list with numbers 1 to n

if (start == nums.size())Base case: all positions fixed, check validity

if (val % pos != 0 && pos % val != 0) return 0;Check divisibility condition for each position

Collections.swap(nums, i, start);Swap elements to generate permutations

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int count = 0;

bool isBeautiful(const vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        int pos = i + 1;
        int val = arr[i];
        if (val % pos != 0 && pos % val != 0) return false;
    }
    return true;
}

void permute(vector<int>& arr, int start) {
    if (start == arr.size()) {
        if (isBeautiful(arr)) count++;
        return;
    }
    for (int i = start; i < arr.size(); i++) {
        swap(arr[i], arr[start]);
        permute(arr, start + 1);
        swap(arr[i], arr[start]);
    }
}

int main() {
    int n = 2;
    vector<int> arr;
    for (int i = 1; i <= n; i++) arr.push_back(i);
    permute(arr, 0);
    cout << count << endl; // Output: 2
    return 0;
}

Line Notes

for (int i = 1; i <= n; i++) arr.push_back(i);Initialize vector with numbers 1 to n

if (start == arr.size())Base case: all positions fixed, check if arrangement is beautiful

if (val % pos != 0 && pos % val != 0) return false;Check divisibility condition for each position

swap(arr[i], arr[start]);Swap elements to generate permutations

function countArrangement(n) {
    let count = 0;
    const nums = [];
    for (let i = 1; i <= n; i++) nums.push(i);

    function permute(arr, start) {
        if (start === arr.length) {
            for (let i = 0; i < arr.length; i++) {
                let pos = i + 1;
                let val = arr[i];
                if (val % pos !== 0 && pos % val !== 0) return;
            }
            count++;
            return;
        }
        for (let i = start; i < arr.length; i++) {
            [arr[i], arr[start]] = [arr[start], arr[i]];
            permute(arr, start + 1);
            [arr[i], arr[start]] = [arr[start], arr[i]];
        }
    }

    permute(nums, 0);
    return count;
}

// Test
console.log(countArrangement(2)); // Output: 2

Line Notes

for (let i = 1; i <= n; i++) nums.push(i);Initialize array with numbers 1 to n

if (start === arr.length)Base case: all positions fixed, check validity

if (val % pos !== 0 && pos % val !== 0) return;Check divisibility condition for each position

[arr[i], arr[start]] = [arr[start], arr[i]];Swap elements to generate permutations

count++Increment count if current permutation is beautiful

⏱

Complexity

TimeO(n! * n)

SpaceO(n)

Generating all permutations takes O(n!) time, and checking each permutation takes O(n) time, resulting in O(n! * n) total time. Space is O(n) for recursion stack and permutation storage.

💡 For n=10, n! is about 3.6 million, so this approach quickly becomes infeasible beyond small n.

Interview Verdict: TLE

This approach times out for larger inputs because it tries all permutations without pruning, demonstrating the need for optimization.

🧠

Backtracking with Pruning

💡 This approach improves efficiency by pruning invalid permutations early during recursion, avoiding full generation of all permutations.

Intuition

Build the arrangement position by position, only placing numbers that satisfy the divisibility condition at the current position, and skipping invalid choices immediately.

Algorithm

1. Start from position 1 and try placing each unused number that satisfies the divisibility condition.
2. Mark the chosen number as used and recurse to the next position.
3. If all positions are filled, increment the count.
4. Backtrack by unmarking the number and trying other candidates.

💡 This algorithm is harder to visualize because it combines recursion with condition checks and state management, but it drastically reduces unnecessary work.

</>

Code

def countArrangement(n: int) -> int:
    count = 0
    used = [False] * (n + 1)

    def backtrack(pos):
        nonlocal count
        if pos > n:
            count += 1
            return
        for num in range(1, n + 1):
            if not used[num] and (num % pos == 0 or pos % num == 0):
                used[num] = True
                backtrack(pos + 1)
                used[num] = False

    backtrack(1)
    return count

# Driver code
if __name__ == '__main__':
    print(countArrangement(2))  # Output: 2

Line Notes

used = [False] * (n + 1)Track which numbers have been used to avoid duplicates

if pos > n:Base case: all positions assigned, increment count

if not used[num] and (num % pos == 0 or pos % num == 0)Prune by only choosing numbers that satisfy divisibility condition

used[num] = FalseBacktrack by unmarking the number for other branches

public class BeautifulArrangement {
    private static int count = 0;

    public static int countArrangement(int n) {
        boolean[] used = new boolean[n + 1];
        backtrack(1, n, used);
        return count;
    }

    private static void backtrack(int pos, int n, boolean[] used) {
        if (pos > n) {
            count++;
            return;
        }
        for (int num = 1; num <= n; num++) {
            if (!used[num] && (num % pos == 0 || pos % num == 0)) {
                used[num] = true;
                backtrack(pos + 1, n, used);
                used[num] = false;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(countArrangement(2)); // Output: 2
    }
}

Line Notes

boolean[] used = new boolean[n + 1];Boolean array to track used numbers

if (pos > n)Base case: all positions assigned, increment count

if (!used[num] && (num % pos == 0 || pos % num == 0))Prune invalid choices early

used[num] = false;Backtrack to explore other permutations

#include <iostream>
#include <vector>
using namespace std;

int count = 0;

void backtrack(int pos, int n, vector<bool>& used) {
    if (pos > n) {
        count++;
        return;
    }
    for (int num = 1; num <= n; num++) {
        if (!used[num] && (num % pos == 0 || pos % num == 0)) {
            used[num] = true;
            backtrack(pos + 1, n, used);
            used[num] = false;
        }
    }
}

int main() {
    int n = 2;
    vector<bool> used(n + 1, false);
    backtrack(1, n, used);
    cout << count << endl; // Output: 2
    return 0;
}

Line Notes

vector<bool> used(n + 1, false);Track used numbers to avoid repeats

if (pos > n)Base case: all positions assigned, increment count

if (!used[num] && (num % pos == 0 || pos % num == 0))Prune invalid candidates early

used[num] = false;Backtrack to try other numbers

function countArrangement(n) {
    let count = 0;
    const used = new Array(n + 1).fill(false);

    function backtrack(pos) {
        if (pos > n) {
            count++;
            return;
        }
        for (let num = 1; num <= n; num++) {
            if (!used[num] && (num % pos === 0 || pos % num === 0)) {
                used[num] = true;
                backtrack(pos + 1);
                used[num] = false;
            }
        }
    }

    backtrack(1);
    return count;
}

// Test
console.log(countArrangement(2)); // Output: 2

Line Notes

const used = new Array(n + 1).fill(false);Boolean array to track used numbers

if (pos > n)Base case: all positions assigned, increment count

if (!used[num] && (num % pos === 0 || pos % num === 0))Prune invalid choices early

used[num] = false;Backtrack to explore other permutations

⏱

Complexity

TimeO(k!) where k ≤ n, pruned by divisibility

SpaceO(n) for recursion and used array

Backtracking prunes many invalid permutations early, reducing the search space significantly compared to brute force. Exact complexity depends on pruning effectiveness.

💡 For n=15, pruning reduces the search space drastically, making this approach feasible in practice.

Interview Verdict: Accepted

This approach is efficient enough for the problem constraints and is the standard solution in interviews.

🧠

Backtracking with Bitmask Optimization

💡 This approach optimizes the used number tracking by using bitmasks instead of arrays, reducing memory usage and potentially speeding up checks.

Intuition

Use an integer bitmask to represent which numbers are used, allowing O(1) checks and updates, while applying the same pruning logic as before.

Algorithm

1. Represent used numbers as bits in an integer mask.
2. At each position, iterate over numbers 1 to n, checking if the bit is unset and divisibility condition holds.
3. Set the bit for chosen number and recurse to next position.
4. Unset the bit on backtracking.

💡 This algorithm is similar to previous backtracking but uses bit operations for efficiency, which can be tricky to implement correctly.

</>

Code

def countArrangement(n: int) -> int:
    count = 0

    def backtrack(pos, used):
        nonlocal count
        if pos > n:
            count += 1
            return
        for num in range(1, n + 1):
            bit = 1 << (num - 1)
            if (used & bit) == 0 and (num % pos == 0 or pos % num == 0):
                backtrack(pos + 1, used | bit)

    backtrack(1, 0)
    return count

# Driver code
if __name__ == '__main__':
    print(countArrangement(2))  # Output: 2

Line Notes

def backtrack(pos, used):Pass current position and bitmask of used numbers

bit = 1 << (num - 1)Create bitmask for current number with correct bit position

if (used & bit) == 0 and (num % pos == 0 or pos % num == 0)Check if number unused and satisfies divisibility

backtrack(pos + 1, used | bit)Recurse with updated bitmask including current number

public class BeautifulArrangement {
    private static int count = 0;

    public static int countArrangement(int n) {
        backtrack(1, 0, n);
        return count;
    }

    private static void backtrack(int pos, int used, int n) {
        if (pos > n) {
            count++;
            return;
        }
        for (int num = 1; num <= n; num++) {
            int bit = 1 << (num - 1);
            if ((used & bit) == 0 && (num % pos == 0 || pos % num == 0)) {
                backtrack(pos + 1, used | bit, n);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(countArrangement(2)); // Output: 2
    }
}

Line Notes

private static void backtrack(int pos, int used, int n)Pass position and bitmask of used numbers

int bit = 1 << (num - 1);Create bitmask for current number with correct bit position

if ((used & bit) == 0 && (num % pos == 0 || pos % num == 0))Check if number unused and satisfies divisibility

backtrack(pos + 1, used | bit, n);Recurse with updated bitmask including current number

#include <iostream>
using namespace std;

int count = 0;

void backtrack(int pos, int used, int n) {
    if (pos > n) {
        count++;
        return;
    }
    for (int num = 1; num <= n; num++) {
        int bit = 1 << (num - 1);
        if ((used & bit) == 0 && (num % pos == 0 || pos % num == 0)) {
            backtrack(pos + 1, used | bit, n);
        }
    }
}

int main() {
    int n = 2;
    backtrack(1, 0, n);
    cout << count << endl; // Output: 2
    return 0;
}

Line Notes

void backtrack(int pos, int used, int n)Pass position and bitmask of used numbers

int bit = 1 << (num - 1);Create bitmask for current number with correct bit position

if ((used & bit) == 0 && (num % pos == 0 || pos % num == 0))Check if number unused and satisfies divisibility

backtrack(pos + 1, used | bit, n);Recurse with updated bitmask including current number

function countArrangement(n) {
    let count = 0;

    function backtrack(pos, used) {
        if (pos > n) {
            count++;
            return;
        }
        for (let num = 1; num <= n; num++) {
            let bit = 1 << (num - 1);
            if ((used & bit) === 0 && (num % pos === 0 || pos % num === 0)) {
                backtrack(pos + 1, used | bit);
            }
        }
    }

    backtrack(1, 0);
    return count;
}

// Test
console.log(countArrangement(2)); // Output: 2

Line Notes

function backtrack(pos, used)Pass current position and bitmask of used numbers

let bit = 1 << (num - 1);Create bitmask for current number with correct bit position

if ((used & bit) === 0 && (num % pos === 0 || pos % num === 0))Check if number unused and satisfies divisibility

backtrack(pos + 1, used | bit);Recurse with updated bitmask including current number

⏱

Complexity

TimeO(k!) with pruning, similar to previous approach

SpaceO(n) recursion stack, O(1) extra for bitmask

Bitmasking reduces memory overhead and can speed up used checks, but overall complexity remains dominated by backtracking search space.

💡 Bitmasking is a common optimization in backtracking problems involving subsets or permutations.

Interview Verdict: Accepted

This approach is a neat optimization that can impress interviewers and is practical for larger n within constraints.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the backtracking with pruning approach is sufficient and efficient. Brute force is useful to explain but not to implement. Bitmasking is a nice optimization if time permits.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Pruning	O(k!) with pruning (k ≤ n)	O(n)	Yes (manageable for n ≤ 15)	Yes	Code this approach
3. Backtracking with Bitmask Optimization	O(k!) with pruning	O(n) recursion, O(1) extra	Yes	Yes	Optional optimization if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain brute force to show understanding, followed by optimized backtracking approaches. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to generate all permutations and check conditions.Step 3: Explain why brute force is inefficient and introduce backtracking with pruning.Step 4: Discuss further optimization using bitmasking for used number tracking.Step 5: Code the backtracking with pruning approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of backtracking, pruning to reduce search space, and ability to implement recursion with state management correctly.

Common Follow-ups

• What if n is very large? → Discuss time complexity and pruning limits.
• Can you generate all beautiful arrangements instead of counting? → Modify code to store permutations.

💡 Follow-ups often test your ability to adapt the solution for variations or analyze scalability.

🔍

Pattern Recognition

When to Use

1) Problem involves permutations or arrangements. 2) Constraints depend on position and element values. 3) Need to count or generate valid sequences. 4) Divisibility or other pruning conditions apply.

Signature Phrases

'number at position i is divisible by i or i is divisible by the number''count the number of valid arrangements'

NOT This Pattern When

Problems that only require generating permutations without constraints or problems solvable by greedy or DP.

Similar Problems

Permutations II - handling duplicates with backtrackingN-Queens - placing queens with constraintsSudoku Solver - constraint satisfaction with backtracking