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

Practice

1. Consider the following BFS-based code snippet for removing invalid parentheses:

from collections import deque

def is_valid(s: str) -> bool:
    count = 0
    for c in s:
        if c == '(': count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

def remove_invalid_parentheses_bfs(s: str):
    res = []
    visited = set([s])
    queue = deque([s])
    found = False

    while queue:
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()
            if is_valid(curr):
                res.append(curr)
                found = True
            if found:
                continue
            for i in range(len(curr)):
                if curr[i] not in ('(', ')'):
                    continue
                next_str = curr[:i] + curr[i+1:]
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_str)
    return res

print(remove_invalid_parentheses_bfs("()())()"))

What is the output of this code?

easy

A. ["()()()"]

B. ["()()()", "(())()"]

C. ["(())()"]

D. ["()())()"]

Solution

1. Step 1: Trace BFS levels for input "()())()"

   Initial string is invalid. BFS removes one parenthesis at each position generating candidates. The first valid strings found are "()()()" and "(())()".

2. Step 2: Confirm both valid strings are collected

   Since BFS stops adding new states after finding valid strings at current level, both minimal removal results are returned.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Both minimal valid strings are returned [OK]

Hint: BFS returns all minimal valid strings at first valid level [OK]

Common Mistakes:

• Returning only one valid string
• Returning original invalid string
• Missing one minimal valid string

2. Consider the following code snippet implementing the optimal backtracking solution for Word Search. Given the board = [["A","B","C"],["D","E","F"],["G","H","I"]] and word = "BEF", what is the return value of exist(board, word)?

easy

A. True

B. False

C. Raises IndexError

D. Infinite recursion

Solution

1. Step 1: Trace dfs starting at cell (0,1) 'B'

   Word starts with 'B', found at (0,1). dfs(0,1,0) matches 'B'.

2. Step 2: Explore neighbors for next chars 'E' and 'F'

   From (0,1), neighbors checked: (1,1) 'E' matches next char, then (1,2) 'F' matches last char. All matched, return True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All characters found sequentially with valid moves [OK]

Hint: Trace dfs calls carefully to confirm path exists [OK]

Common Mistakes:

• Assuming no path due to adjacency confusion
• Missing in-place marking effect

3. What is the time complexity of the optimal backtracking solution for the Expression Add Operators problem, where n is the length of the input string? Assume the solution tries all operator insertions and substring splits with pruning and efficient string building.

medium

A. O(4^n) because at each position there are up to 4 choices (3 operators + no operator split)

B. O(n * 3^n) because each digit can be combined with 3 operators and substring splits

C. O(2^n) since only two operators are considered at each step

D. O(n^3) due to substring parsing and operator insertions

Solution

1. Step 1: Identify branching factor per digit

   At each digit, we can insert one of 3 operators (+, -, *) or choose to extend the current operand (no operator), but the main branching factor is 3 operators per split, and substring splits add a factor of n.

2. Step 2: Calculate total complexity

   The total complexity is roughly O(n * 3^n) because for each of the n positions, there are up to 3 operator choices, and substring splits add an n factor.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Exponential branching with 3 operators and substring splits [OK]

Hint: 3 operators per digit and substring splits lead to O(n * 3^n) complexity [OK]

Common Mistakes:

• Confusing substring parsing cost as cubic
• Assuming only 2 operators reduce complexity
• Miscounting branching factor as 4

4. Consider the following code snippet intended to generate unique permutations of an array with duplicates. Which line contains a subtle bug that causes duplicate permutations to be generated?

def permuteUnique(nums):
    nums.sort()
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    return res

medium

A. Line with 'if i > start and nums[i] == nums[i-1]: continue' (duplicate skipping condition)

B. Line with 'nums.sort()' (sorting input before recursion)

C. Line with 'nums[start], nums[i] = nums[i], nums[start]' before recursion (swap)

D. Line with 'for i in range(start, len(nums)):' (iteration over indices)

Solution

1. Step 1: Analyze duplicate skipping condition

   The condition 'if i > start and nums[i] == nums[i-1]: continue' attempts to skip duplicates but does not consider whether the previous duplicate was used, causing some duplicates to be missed.

2. Step 2: Verify other lines

   Sorting input is correct; swapping before and after recursion is correct; iteration over indices is standard. The bug is in the duplicate skipping logic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect duplicate skipping causes duplicate permutations [OK]

Hint: Skipping duplicates requires tracking usage, not just comparing adjacent elements [OK]

Common Mistakes:

• Skipping duplicates by only comparing adjacent elements without usage tracking

5. Suppose the N-Queens problem is modified so that queens can be placed multiple times in the same column (i.e., column conflicts are ignored), but diagonal conflicts still apply. Which modification to the bitmask backtracking approach correctly counts all valid solutions under this relaxed constraint?

hard

A. Track only column bitmask and ignore diagonal bitmasks

B. Keep all bitmasks but allow queens to be placed in any column regardless of conflicts

C. Remove the column bitmask and only track diagonal bitmasks for conflicts

D. Use a greedy approach placing queens in the first available diagonal position per row

Solution

1. Step 1: Analyze relaxed constraints

   Column conflicts are ignored, so column bitmask is unnecessary; diagonal conflicts remain.

2. Step 2: Modify bitmask tracking accordingly

   Remove column bitmask from conflict checks and recursive calls; keep positive and negative diagonal bitmasks to prune invalid placements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Removing column mask matches relaxed rules and preserves diagonal conflict checks [OK]

Hint: Ignore column mask when column conflicts are allowed [OK]

Common Mistakes:

• Ignoring diagonals too
• Allowing all placements without pruning