Beautiful Arrangement

📋

Problem

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?

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

Edge cases: n = 1 → output: 1 (only one number, trivially beautiful)n = 0 → output: 0 (no numbers, no arrangements)n = 15 → output: large number, tests efficiency

</>

IDE

def countArrangement(n: int) -> int:public int countArrangement(int n)int countArrangement(int n)function countArrangement(n)

def countArrangement(n: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int countArrangement(int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int countArrangement(int n) {
    // Write your solution here
    return 0;
}

function countArrangement(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for all inputs due to missing base case or incorrect initialization.✅ Add explicit base case: if n == 0: return 0; initialize count properly.

Wrong: 1Always returning 1 regardless of input, ignoring permutations and divisibility checks.✅ Implement full backtracking with divisibility checks instead of constant return.

Wrong: Incorrect count less than expectedGreedy approach that picks numbers without exploring all valid permutations.✅ Use backtracking with pruning instead of greedy selection.

Wrong: Count greater than expectedReusing numbers multiple times, ignoring 0/1 usage constraint.✅ Track used numbers with boolean array or bitmask to avoid reuse.

Wrong: Wrong count due to off-by-one errorsUsing zero-based indexing inconsistently for positions and numbers in divisibility checks.✅ Use 1-based indexing consistently for positions and numbers.

✓

Test Cases

Focus on handling base cases and boundary inputs correctly.

Ensure your backtracking logic is robust and handles all constraints precisely.

Optimize your solution to handle the largest input efficiently using pruning.

t1_01basic

Input{"n":2}

Expected2

⏱ Performance - must finish in 2000ms

The two beautiful arrangements are [1,2] and [2,1]. Both satisfy the divisibility conditions at each position.

💡 Consider all permutations of numbers from 1 to n.

💡 Check divisibility conditions for each position and number pair.

💡 Count permutations where for every position i, number divides i or i divides number.

Why it failed: Incorrect count for n=2 indicates failure to check divisibility conditions properly. Fix by ensuring both conditions (num % i == 0 or i % num == 0) are checked for each position.

✓ Correctly counts all valid permutations for n=2.

t1_02basic

Input{"n":3}

Expected3

⏱ Performance - must finish in 2000ms

The three beautiful arrangements for n=3 are [1,2,3], [3,2,1], and [2,1,3].

💡 Try enumerating permutations for n=3 and apply divisibility rules.

💡 Use backtracking with pruning to avoid invalid permutations early.

💡 Count only permutations where each position satisfies divisibility conditions.

Why it failed: Wrong output for n=3 usually means missing some valid permutations or including invalid ones. Fix by pruning permutations that violate divisibility at any position.

✓ Correctly counts all valid permutations for n=3.

t2_01edge

Input{"n":0}

Expected1

⏱ Performance - must finish in 2000ms

No numbers means no arrangements, so the count is 0.

💡 Consider the base case where no numbers are given.

💡 No permutations exist for n=0.

💡 Return 0 immediately when n is zero.

Why it failed: Returning non-zero for n=0 indicates missing base case handling. Fix by adding a condition to return 0 when n=0.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"n":1}

Expected1

⏱ Performance - must finish in 2000ms

Only one number and one position, trivially satisfying the divisibility condition.

💡 For n=1, only one permutation exists.

💡 Check divisibility condition for position 1 and number 1.

💡 Return 1 for n=1 as the base case.

Why it failed: Incorrect output for n=1 means base case not handled or divisibility check incorrect. Fix by returning 1 when n=1.

✓ Correctly returns 1 for single element input.

t2_03edge

Input{"n":15}

Expected24679

⏱ Performance - must finish in 2000ms

Maximum input size to test efficiency and correctness; known result is 24679.

💡 Use pruning to reduce search space for large n.

💡 Backtracking with divisibility checks is essential for performance.

💡 Avoid generating all permutations explicitly for n=15.

Why it failed: Incorrect output or timeout for n=15 indicates inefficient or incorrect pruning. Fix by implementing pruning to skip invalid permutations early.

✓ Correctly computes count for n=15 using pruning.

t3_01corner

Input{"n":4}

Expected8

⏱ Performance - must finish in 2000ms

For n=4, the count is 8. This test catches greedy approach failures.

💡 Greedy selection of numbers by position may miss valid permutations.

💡 Backtracking with full search and pruning is required.

💡 Avoid choosing numbers greedily; explore all valid options.

Why it failed: Output less than 8 indicates greedy approach missed valid permutations. Fix by implementing full backtracking with pruning instead of greedy selection.

✓ Correctly counts all valid permutations for n=4, avoiding greedy traps.

t3_02corner

Input{"n":5}

Expected10

⏱ Performance - must finish in 2000ms

For n=5, the count is 10. This test catches confusion between 0/1 and unbounded usage of numbers.

💡 Each number can be used only once (0/1 knapsack style).

💡 Do not reuse numbers in multiple positions.

💡 Track used numbers carefully to avoid duplicates.

Why it failed: Output greater than 10 indicates numbers reused multiple times. Fix by marking numbers as used and not reusing them in other positions.

✓ Correctly counts permutations with each number used exactly once.

t3_03corner

Input{"n":6}

Expected36

⏱ Performance - must finish in 2000ms

For n=6, the count is 36. This test catches off-by-one errors in indexing positions or numbers.

💡 Positions are 1-indexed, be careful with zero-based arrays.

💡 Check divisibility conditions using (i+1) or i carefully.

💡 Ensure loops and checks align with 1-based indexing.

Why it failed: Incorrect output due to off-by-one errors in indexing positions or numbers. Fix by consistently using 1-based indexing for positions and numbers in divisibility checks.

✓ Correctly handles 1-based indexing for positions and numbers.

t4_01performance

Input{"n":15}

Expectednull

⏱ Performance - must finish in 2000ms

Input n=15 tests performance of backtracking with pruning. Algorithm must complete within 2 seconds.

💡 Brute force permutation generation is O(n!).

💡 Use pruning to reduce search space drastically.

💡 Bitmask or boolean array can optimize used number tracking.

Why it failed: TLE indicates exponential brute force without pruning. Fix by implementing pruning and efficient used number tracking to reduce complexity.

✓ Algorithm completes within time limit using pruning and efficient backtracking.