Total xor

You are given an array of integers. Write a script to return the sum of total XOR for every subset of given array.

Examples

Example 1
Input: @ints = (1, 3)
Output: 6
Subset [1],    total XOR = 1
Subset [3],    total XOR = 3
Subset [1, 3], total XOR => 1 XOR 3 => 2
Sum of total XOR => 1 + 3 + 2 => 6

Example 2
Input: @ints = (5, 1, 6)
Output: 28
Subset [5],       total XOR = 5
Subset [1],       total XOR = 1
Subset [6],       total XOR = 6
Subset [5, 1],    total XOR => 5 XOR 1 => 4
Subset [5, 6],    total XOR => 5 XOR 6 => 3
Subset [1, 6],    total XOR => 1 XOR 6 => 7
Subset [5, 1, 6], total XOR => 5 XOR 1 XOR 6 => 2
Sum of total XOR => 5 + 1 + 6 + 4 + 3 + 7 + 2 => 28

Example 3
Input: @ints = (3, 4, 5, 6, 7, 8)
Output: 480

Analysis

Rather than reinvent the wheel, I have use my favourite perms and combs module, Algorithm::Combinatorics, to generate the subsets. All that is needed then is two nested loops, the outer one over all the subsets and the inner one doing the XOR operation using Perl's ^ operator.

On my computer this gives an answer within a few seconds for an array of up to about 18 elements.

For any array of n random elements in a range of 1 to 2**n - 1, the result of sum has a maximum value, and that maximum value will be met by a large proportion of such arrays. For example, if n == 6 and the elements are in the range 1 .. 15 the maximum is 480 and you can see from my choice of examples that this is achieved for a range of input values. Only when I deliberately chose only even numbers did the total reduce by 32 to 448.

The post stands out for its clarity, depth, and instructional value. His explanations are accessible, making complex concepts understandable for a broad audience. The code is well-structured and annotated, providing readers with valuable insights into Perl programming and problem-solving techniques.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-06-02
use utf8;     # Week 324 - task 2 - Total xor
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;
use Algorithm::Combinatorics 'subsets';

total_xor(5, 1, 6);
total_xor(3, 4, 5, 6, 7, 8);
total_xor(1, 3, 6, 8, 9, 15);
total_xor(7, 8, 9, 10, 11, 12);
total_xor(2, 4, 6, 8, 10, 12);

# bigger example
my @array;
push @array, int(rand(2000)) for 0 .. 16;
total_xor(@array);

sub total_xor {
    
    my (@array, $total, $iter, $subtotal, $s, $i);
    
    # initialise
    @array = @_;
    $total = 0;
    $iter = subsets(\@array);
    
    # iterate over subsets
    while ($s = $iter->next) {
        $subtotal = 0;
        $subtotal = $subtotal ^ $_ for @$s;
        $total += $subtotal;
    }
    
    # report
    say qq[\nInput:  \@array = (] . join(', ', @array) . ')';
    say qq[Output: $total];
}

11 lines of code

Output from script

Input:  @array = (5, 1, 6)
Output: 28

Input:  @array = (3, 4, 5, 6, 7, 8)
Output: 480

Input:  @array = (1, 3, 6, 8, 9, 15)
Output: 480

Input:  @array = (7, 8, 9, 10, 11, 12)
Output: 480

Input:  @array = (2, 4, 6, 8, 10, 12)
Output: 448

Input:  @array = (1284, 851, 1990, 513, 453, 1738, 1882, 1133, 1250, 839, 815, 749, 924, 1669, 60, 1555, 215)
Output: 134152192