Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 526 with 15 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 526 # by problem number
lcpy gen -s beautiful_arrangement # by problem name
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].n, return the number of the beautiful arrangements that you can construct.
Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1,2]:
- perm[1] = 1 is divisible by i = 1
- perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm[1] = 2 is divisible by i = 1
- i = 2 is divisible by perm[2] = 1
Input: n = 1
Output: 1
1 <= n <= 15class Solution:
# Time: O(n * 2^n)
# Space: O(2^n)
def count_arrangement(self, n: int) -> int:
full = (1 << n) - 1
memo: dict[int, int] = {}
def count(mask: int) -> int:
if mask == full:
return 1
if mask in memo:
return memo[mask]
pos = mask.bit_count() + 1
total = 0
for value in range(1, n + 1):
bit = 1 << (value - 1)
if not mask & bit and (value % pos == 0 or pos % value == 0):
total += count(mask | bit)
memo[mask] = total
return total
return count(0)
| Time | Space |
|---|---|
| O(n * 2^n) | O(2^n) |