Third highest and maximum xor

Weekly challenge 205 — 20 February 2023

Week 205 - 20 Feb 2023

Task 2

You are given an array of integers. Write a script to find the highest value obtained by XORing any two distinct members of the array.

The first thing to note - and I had to look it up - is that Perl does have an xor operator - ^ - so the obvious way to do the task is by using two nested loops:

for $i (0 .. $count - 2) { for $j ($i + 1 .. $count - 1) { ... calculate $array[$i] ^ $array[$j] and keep track of the maximum value

But is this the best way? Suppose we look for the largest number in @array and count its binary digits. For example, if the largest number is 25, that's 11001 in binary, which is 5 binary digits. Clearly the xor of any two numbers in @array cannot exceed 11111, which is 31 or 2**5 - 1, because if the largest number in the array has 5 binary digits, no other number can have a sixth. So in the inner loop we can stop as soon as we hit a pair of numbers which xor to 31: we know no other pair can exceed that.

In an arbitrary array there may of course be several pairs which xor to the maximum. In Mohammad's third example - 10, 5, 7, 12, 8 - he shows 10 ^ 5 = 15, but equally 7 ^ 8 = 15, so I think we can take it that showing a single pair meets the conditions stated.

This saving is significant unless the numbers in @array are quite sparse. For example, with an array of 20 random numbers in the range 0 to 63 (6 binary digits) a pair which xor to 63 occurs in about 90% of trials. Increasing the range to 0 to 127 still finds a pair that xors to 127 in ~70% of cases.

In fact, it can easily be shown that if the largest number in @array consists of n binary digits, then any @array containing at least n/2 + 1 unique numbers will contain a pair which xor to the maximum, ie 2**n - 1. So, for example, any 9 numbers in the range 0..15 will contain a pair which xors to 15.

#!/usr/bin/perl # Peter Campbell Smith - 2023-02-20 use v5.28; use utf8; use warnings; use List::Uniq ':all'; # Task: You are given an array of integers. Write a script to find the highest value obtained # by XORing any two distinct members of the array. # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/205/2 my ($j, @test); max_xor(1, 2, 3, 4, 5, 6, 7); max_xor(2, 4, 1, 3); max_xor(10, 5, 7, 12, 8); max_xor(21, 25); max_xor(32, 32, 32, 32); for $j (1 .. 20) { @test[$j - 1] = int(rand(126)) + 1; } max_xor(@test); sub max_xor { my ($count, $i, $j, $max, $xor, $result, @array, $largest, $limit); @array = @_; $count = scalar @array; # find the largest number in the array $largest = 0; for $j (@array) { $largest = $j if $j > $largest; } # find the largest possible xor for $j (1 .. 31) { next unless 2 ** $j > $largest; $limit = 2 ** $j - 1; last; } # now scan for the largest xor $max = -1; if ($count >= 2) { SCAN: for $i (0 .. $count - 2) { for $j ($i + 1 .. $count - 1) { $xor = $_[$i] ^ $_[$j]; if ($xor > $max) { $result = qq[$array[$i] xor $array[$j] = $xor]; $max = $xor; last SCAN if $max == $limit; } } } say qq[\nInput: \@array = (] . join(', ', @_) . ')' . qq[\nOutput: $result]; } else { say 'Array must contan at least 2 elements.' } }

Input: @array = (1, 2, 3, 4, 5, 6, 7) Output: 1 xor 6 = 7 Input: @array = (2, 4, 1, 3) Output: 4 xor 3 = 7 Input: @array = (10, 5, 7, 12, 8) Output: 10 xor 5 = 15 Input: @array = (21, 25) Output: 21 xor 25 = 12 Input: @array = (32, 32, 32, 32) Output: 32 xor 32 = 0 Input: @array = (75, 71, 95, 36, 76, 54, 51, 74, 93, 72, 27, 89, 120, 98, 96, 21, 13, 60, 104, 43) Output: 76 xor 51 = 127

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain