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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Beautiful Arrangement

Number: 526

Difficulty: Medium

Paid? No

Companies: Amazon, HashedIn, Salesforce, Nvidia, Google

Problem Description

Given an integer n, count the number of beautiful arrangements that can be constructed. A beautiful arrangement is a permutation perm (1-indexed) of numbers from 1 to n such that for every position i (1 ≤ i ≤ n), either perm[i] is divisible by i or i is divisible by perm[i].

Key Insights

  • The condition for a beautiful arrangement allows early pruning: only select numbers that satisfy the divisibility rule with the current position.
  • Backtracking (DFS) can be used to generate valid permutations, which is feasible as n is at most 15.
  • Bitmasking is an effective technique to track used numbers and optimize the backtracking process.

Space and Time Complexity

Time Complexity: O(n!) in the worst-case scenario although pruning reduces the practical number of iterations. Space Complexity: O(n) due to recursion stack and auxiliary space for the bitmask.

Solution

The approach uses depth-first search (DFS) with backtracking to generate all possible valid arrangements. At each position i (from 1 to n), we iterate through all possible numbers (1 to n) that have not yet been used. We check if the chosen number meets the beautiful arrangement condition with the current position. A bitmask is utilized to efficiently track which numbers have been used. When all positions are filled (i > n), a valid arrangement is found. This solution leverages both backtracking to explore potential arrangements and bit manipulation to maintain state efficiently.

Code Solutions

def countArrangement(n: int) -> int:
    # Helper function: performs DFS with current position and bitmask representing used numbers.
    def dfs(pos, used):
        # Base Case: If all positions are filled, a valid arrangement is formed.
        if pos > n:
            return 1
        total = 0
        # Iterate through each number to see if it can be placed at position pos.
        for num in range(1, n + 1):
            # Check if 'num' hasn't been used and satisfies the condition with position 'pos'.
            if not (used & (1 << num)) and (num % pos == 0 or pos % num == 0):
                total += dfs(pos + 1, used | (1 << num))
        return total

    return dfs(1, 0)

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