The Bear's Den

Enter at your own risk

06 June 2025 Challenge 324

Or Is It Reshaped?

Task 1: 2D Array

Submitted by: Mohammad Sajid Anwar

You are given an array of integers and two integers $r and $c.

Write a script to create two dimension array having $r rows and $c columns using the given array.

Example 1

Input: @ints = (1, 2, 3, 4), $r = 2, $c = 2
Output: ([1, 2], [3, 4])

Example 2

Input: @ints = (1, 2, 3), $r = 1, $c = 3
Output: ([1, 2, 3])

Example 3

Input: @ints = (1, 2, 3, 4), $r = 4, $c = 1
Output: ([1], [2], [3], [4])

Solution

Using PDL’s reshape method, this task can easily be solved.

This works even if the product $r * $c does not match the number of elements in the array. The result will be truncated or filled with zeroes accordingly.

use strict;
use warnings;
use experimental 'signatures';
use PDL;

sub two_d_array ($r, $c, @ints) {
    pdl(@ints)->reshape($c, $r);
}

See the full solution to task 1.

Task 2: Total XOR

Submitted by: Mohammad Sajid Anwar

You are given an array of integers.

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

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

Solution

Preliminary Considerations

There is a little ambiguity in this task that may lead to significantly different results.

We are given an array of integers and shall iterate over the subsets thereof. No definition for subsets of an array is given and I’m not aware of any, so I have to make assumptions. There are several ways to define subsets of an array. I’ll give some examples and show the results on the array (1, 1, 1).

  1. Subsets are parts of sets: unordered collections of unique items. Applying this concept to the example array leads to two subsets \(\{\emptyset, \{1\}\}\) and a total XOR sum of \(1\).
  2. We may look at the array as a multiset and iterate over submultisets thereof. Here we find the submultisets \(\{\emptyset, [1], [1, 1], [1, 1, 1]\}\) and a total XOR sum of \(2\).
  3. We may iterate over index subsets. These are well-defined as the indices of an array form a proper set. Then we use array slices as the “subsets”. Though this interpretation might look a bit strange from a mathematical point of view, it is exactly what we get when using e.g. Math::Prime::Util’s forcomb function: 
    $ perl -Mntheory=:all -E '@i = (1) x 3; forcomb {say "(@i[@_])"} @i'
()
(1)
(1)
(1)
(1 1)
(1 1)
(1 1)
(1 1 1)

    with a total XOR sum of \(4\).

For now I’ll ignore this issue and presume the integers to be distinct. In this case all three interpretations lead to the same result. See Generalization.

Calculating the total XOR sum

At first glance this task looks expensive, but it isn’t. Interestingly, we neither need to iterate over subsets, nor do we need to perform an XOR operation at all.

We may look at the task from a different angle and consider a single bit position \(i\) within the elements of the subsets. We may count the number of subsets where the XOR over its elements has a 1 at position \(i\). To this end we should count the number \(b_i\) of integers having a 1 at bit position \(i\) and apply some combinatorics to get the number \(o_i\) of subsets having an odd number of 1’s at position \(i\).

Then the total XOR sum would be \(\sum_{i=0}^k o_i 2^i\), iterating over bit positions instead of subsets.

But things get even better! It turns out that the number \(o_i\) doesn’t depend much on the number \(b_i\). In fact, either there is no such subset - when none of the given integers has a 1 at bit position \(i\) - or there are \(2^{n - 1}\) such subsets (with \(n\) as the number of given integers).

To see this, let’s assume there is at least one integer \(p\) having a 1 at bit position \(i\). We can build the power set of the integers with \(p\) excluded. There are \(2^{n - 1}\) sets in this power set. With each set from the power set we either keep it as-is if it has an odd number of 1’s at position \(i\), or we add the previously excluded \(p\) to the subset turning the number of 1’s to odd. The thus constructed set has \(2^{n - 1}\) elements and contains exactly all subsets with an odd number of 1’s at position \(i\).

The opposite case when there is no integer having a 1 at bit position \(i\) set is trivial.

The bit positions where at least one integer has a 1 can be found by taking the bit-wise OR over the given integers. Multiplied with \(2^{n - 1}\) it gives the total XOR sum.

Generalization

Having found an efficient way to calculate the total XOR sum, we may come back to the initial issue: What are the subsets of an array?

It turns out that our approach has the same subset interpretation as forcomb. For the sake of convenience we simply choose the third interpretation for this task and are done.

Implementation

For large arrays (more than 32 long integers) an implementation use‘ing bigint would be required.

use strict;
use warnings;
use PDL;

sub total_xor {
    longlong(@_)->bor->shiftleft(@_ - 1);
}

See the full solution to task 2.

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.