Beautiful Arrangement - Practice Coding Problems

Beautiful Arrangement - Problem

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.

Input & Output

Example 1 — Small Case

$ Input: n = 2

› Output: 2

💡 Note: Both [1,2] and [2,1] are beautiful: 1%1=0, 2%2=0 for first; 2%1=0, 1%2≠0 but 2%1=0 for second

Example 2 — Moderate Case

$ Input: n = 3

› Output: 2

💡 Note: Valid arrangements are [2,1,3] and [3,2,1]. For [2,1,3]: 2%1=0, 1%2≠0 but 2%1=0, 3%3=0. All conditions satisfied.

Example 3 — Single Element

$ Input: n = 1

› Output: 1

💡 Note: Only arrangement [1] where 1%1=0, so it's beautiful

Constraints

1 ≤ n ≤ 15

Visualization

Tap to expand

Understanding the Visualization

Input

Integer n representing range [1,2,...,n]

Check Rule

For each position i, either perm[i] % i == 0 OR i % perm[i] == 0

Count Valid

Return total number of beautiful arrangements

Key Takeaway

🎯 Key Insight: Backtracking with early pruning eliminates invalid arrangements without full exploration

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use backtracking with early pruning to avoid generating invalid arrangements. The beautiful arrangement condition (either perm[i] % i == 0 OR i % perm[i] == 0) allows us to skip many branches during recursion. Best approach is backtracking with memoization using bitmask to represent used numbers. Time: O(k), Space: O(n) where k is the actual number of valid arrangements.

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Permutations	O(n! × n)	O(n)	Generate all n! permutations and count valid beautiful arrangements
Backtracking with Pruning	O(k)	O(n)	Build arrangements position by position, pruning invalid paths early
Memoized Backtracking	O(n × 2ⁿ)	O(n × 2ⁿ)	Cache results of subproblems using bitmask to represent used numbers

Generate All Permutations — Algorithm Steps

Generate all permutations of [1,2,...,n]
For each permutation, check if perm[i] % i == 0 OR i % perm[i] == 0 for all i
Count permutations that satisfy all conditions

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All

Create all n! permutations

Check Each

Validate beautiful arrangement conditions

Count Valid

Count arrangements that satisfy all rules

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int count = 0;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permute(int* arr, int start, int end) {
    if (start == end) {
        int valid = 1;
        for (int i = 0; i <= end; i++) {
            if (arr[i] % (i + 1) != 0 && (i + 1) % arr[i] != 0) {
                valid = 0;
                break;
            }
        }
        if (valid) count++;
        return;
    }
    
    for (int i = start; i <= end; i++) {
        swap(&arr[start], &arr[i]);
        permute(arr, start + 1, end);
        swap(&arr[start], &arr[i]);
    }
}

int solution(int n) {
    count = 0;
    int* arr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    
    permute(arr, 0, n - 1);
    free(arr);
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

Generate n! permutations, check n conditions for each

⚠ Quadratic Growth

Space Complexity

O(n)

Array to store current permutation

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler