The Weekly Challenge 300

Beautiful Arrangement & Nested Array

Solutions on GitHub

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