The Weekly Challenge 059

Partition List and Bit Sum

Solutions on GitHub

Task 1: Partition List

Given a linked list and a value k, partition it such that all nodes less than k come before nodes greater than or equal to k, preserving original relative order.

Example Output

Original list: 1 → 4 → 3 → 2 → 5 → 2 → END Partitioned list with k=3: 1 → 2 → 2 → 4 → 3 → 5 → END

Logic

Maintain two separate linked lists (one for nodes < k and one for nodes ≥ k). Traverse the original list, append each node to the appropriate list, and join the two lists at the end.

Perl Solution

ch-1.pl

sub partition { my ( $self, $k ) = @_; my ( $less_head, $greater_head, $less_tail, $greater_tail ); my $current = $self; while ( defined $current ) { if ( $current->{value} < $k ) { defined $less_tail ? ($less_tail->{next} = $current) : ($less_head = $current); $less_tail = $current; } else { defined $greater_tail ? ($greater_tail->{next} = $current) : ($greater_head = $current); $greater_tail = $current; } $current = $current->{next}; } $less_tail ? ($less_tail->{next} = $greater_head) : ($less_head = $greater_head); $greater_tail->{next} = undef if defined $greater_tail; return $less_head; }

Python Solution

ch-1.py

def partition(self, k): less_head = greater_head = less_tail = greater_tail = None current = self while current: if current.value < k: if less_tail: less_tail.next = current else: less_head = current less_tail = current else: if greater_tail: greater_tail.next = current else: greater_head = current greater_tail = current current = current.next if less_tail: less_tail.next = greater_head else: less_head = greater_head if greater_tail: greater_tail.next = None return less_head

Task 2: Bit Sum

Given an array of positive integers, calculate the sum of bit differences between all pairs of integers in the array.

Example Output

Input: [2, 3, 4] Output: 6

Logic

For every pair of numbers (a, b) in the array, count the number of set bits in a ^ b (XOR), and sum these count values across all pairs.

Perl Solution

ch-2.pl

sub count_different_bits { my ( $a, $b ) = @_; my $count = 0; while ( $a > 0 or $b > 0 ) { $count += ( $a % 2 ) ^ ( $b % 2 ); $a >>= 1; $b >>= 1; } return $count; } sub sum_different_bits { my @numbers = @_; my $sum = 0; for my $i ( 0 .. $#numbers ) { for my $j ( $i + 1 .. $#numbers ) { $sum += count_different_bits( $numbers[$i], $numbers[$j] ); } } return $sum; }

Python Solution

ch-2.py

def count_different_bits(a: int, b: int) -> int: count = 0 while a > 0 or b > 0: count += (a % 2) ^ (b % 2) a >>= 1 b >>= 1 return count def sum_different_bits(numbers: List[int]) -> int: total = 0 for i in range(len(numbers)): for j in range(i+1, len(numbers)): total += count_different_bits(numbers[i], numbers[j]) return total