We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Beautiful Arrangement

Difficulty: Medium

Problem Description

Given an integer n, return the number of beautiful arrangements that can be constructed using integers labeled from 1 to n. A permutation is considered a beautiful arrangement if for every index i (1 <= i <= n), either perm[i] is divisible by i or i is divisible by perm[i].

Key Insights

  • A beautiful arrangement requires checking divisibility conditions for each position in the permutation.
  • The problem can be solved using backtracking to explore all possible permutations of the integers.
  • The constraints (1 <= n <= 15) allow for a factorial number of permutations, making backtracking feasible.

Space and Time Complexity

Time Complexity: O(n!), because we may need to generate all permutations of n elements. Space Complexity: O(n), for storing the current permutation and a visited array to track used integers.

Solution

The solution employs a backtracking algorithm to generate all permutations of the numbers from 1 to n. For each index in the permutation, we check the divisibility conditions. If the current arrangement meets the criteria, we proceed to the next index. If we reach the end of the permutation, we count it as a valid arrangement.

Code Solutions

def countArrangement(n):
    def backtrack(pos, visited):
        if pos > n:
            return 1
        count = 0
        for i in range(1, n + 1):
            if not visited[i] and (i % pos == 0 or pos % i == 0):
                visited[i] = True
                count += backtrack(pos + 1, visited)
                visited[i] = False
        return count
    
    visited = [False] * (n + 1)
    return backtrack(1, visited)

# Example usage:
print(countArrangement(2))  # Output: 2
← Back to All Questions