Task 1: Beautiful Arrangement
You are given a positive integer $n. A permutation of numbers 1..$n is considered beautiful if for every position i (1-indexed), either the number at position i is divisible by i, or i is divisible by the number at position i. Return the total count of beautiful arrangements.
Example Output
Input: $n = 2
Output: 2
Explanation:
[1, 2] is beautiful:
- pos 1: 1 % 1 == 0
- pos 2: 2 % 2 == 0
[2, 1] is beautiful:
- pos 1: 2 % 1 == 0
- pos 2: 2 % 1 == 0
Input: $n = 1
Output: 1
Input: $n = 10
Output: 700
Logic
We use depth-first backtracking with bitmask state and memoization. First, we precompute the valid candidates for each position 1..n where val % pos == 0 || pos % val == 0. Then, we place numbers position by position, tracking available numbers with a bitmask integer. In Python we can memoize with @lru_cache; in Perl we use a hash key "$pos:$mask".
Perl Solution
ch-1.pl
sub beautiful_arrangements ($n) {
($n) = $INT_CHECK->($n);
die 'Expected a positive integer' if $n <= 0;
my @allowed;
for my $pos ( 1 .. $n ) {
$allowed[$pos] = [ grep { $_ % $pos == 0 || $pos % $_ == 0 } 1 .. $n ];
}
my %memo;
my $full_mask = ( 1 << $n ) - 1;
my $dfs;
$dfs = sub ($pos, $mask) {
return 1 if $pos > $n;
my $key = "$pos:$mask";
return $memo{$key} if exists $memo{$key};
my $count = 0;
for my $val ( @{ $allowed[$pos] } ) {
my $bit = 1 << ( $val - 1 );
next if ( $mask & $bit ) == 0;
$count += $dfs->( $pos + 1, $mask ^ $bit );
}
return $memo{$key} = $count;
};
return $dfs->( 1, $full_mask );
}
Python Solution
ch-1.py
def beautiful_arrangements(n: int) -> int:
if n <= 0:
raise ValueError("Expected a positive integer")
allowed: list[list[int]] = [
[],
*[
[val for val in range(1, n + 1) if val % pos == 0 or pos % val == 0]
for pos in range(1, n + 1)
],
]
full_mask = (1 << n) - 1
@lru_cache(maxsize=None)
def dfs(pos: int, mask: int) -> int:
if pos > n:
return 1
total = 0
for val in allowed[pos]:
bit = 1 << (val - 1)
if mask & bit:
total += dfs(pos + 1, mask ^ bit)
return total
return dfs(1, full_mask)
Task 2: Nested Array
You are given an array of integers @ints of length n which is a permutation of the numbers in the range [0, n - 1]. Form a set S[i] = { ints[i], ints[ints[i]], ints[ints[ints[i]]], ... } until a duplicate is encountered. Return the longest length of a set S[i].
Example Output
Input: @ints = (5, 4, 0, 3, 1, 6, 2)
Output: 4
Explanation:
ints[0] = 5, ints[5] = 6, ints[6] = 2, ints[2] = 0 -> S[0] = {5, 6, 2, 0} has length 4.
Input: @ints = (0, 1, 2)
Output: 1
Logic
Every element points to another index, and because the array is a permutation of 0..n-1, the permutation graph consists of disjoint cycles. Finding the longest sequence S[i] is equivalent to finding the maximum cycle length in the graph. We keep a visited boolean array to traverse each cycle once in O(n) overall time.
Perl Solution
ch-2.pl
sub nested_array_max ($ints) {
($ints) = $LIST_CHECK->($ints);
my $n = scalar @$ints;
return 0 if $n == 0;
my @visited = (0) x $n;
my $best = 0;
for my $i ( 0 .. $n - 1 ) {
next if $visited[$i];
my $cur = $i;
my %seen_in_walk;
my $len = 0;
while ( !$visited[$cur] && !$seen_in_walk{$cur}++ ) {
++$len;
$cur = $ints->[$cur];
}
# Mark the entire component as visited
$cur = $i;
while ( !$visited[$cur] ) {
$visited[$cur] = 1;
$cur = $ints->[$cur];
}
$best = $len if $len > $best;
}
return $best;
}
Python Solution
ch-2.py
def nested_array_max(ints: Sequence[int]) -> int:
n = len(ints)
if n == 0:
return 0
visited = [False] * n
best = 0
for start in range(n):
if visited[start]:
continue
seen_in_walk: set[int] = set()
current = start
length = 0
while not visited[current] and current not in seen_in_walk:
seen_in_walk.add(current)
length += 1
current = ints[current]
# mark component
current = start
while not visited[current]:
visited[current] = True
current = ints[current]
if length > best:
best = length
return best