Special and unique numbers

Weekly challenge 252 — 15 January 2024

Week 252 - 15 Jan 2024

Task 2

You are given an integer, $n. Write a script to find an array containing $n unique integers such that they add up to zero.

Example 1Input: $n = 5 Output: (-7, -1, 1, 3, 4) Two other possible solutions could be as below: (-5, -1, 1, 2, 3) and (-3, -1, 2, -2, 4).Example 2Input: $n = 3 Output: (-1, 0, 1)Example 3Input: $n = 1 Output: (0)

I've provided two ways of approaching this.

Method one, for odd `$n`

simply returns all the integers from

`($n - 1) / 2`

down to `-($n - 1) / 2`

, and for even `$n`

does the same
but omits zero.

So, for example for `$n == 4`

it returns
`3, 2, 1, -1, -2, -3`

and for `$n == 7`

it returns
`3, 2, 1, 0, -1, -2, -3`

.

Method two generates `$n - 1`

random but unique integers in
the range `-$n`

to `+$n`

, and then appends minus the sum of these
as its final number, making the overall sum zero.

There is a slight
problem to this, though, in that that final number might
already be in the array and thus not be unique, so if that
happens, it simply tries again. There will always be an answer,
because there are many sets of the original `$n - 1`

integers
whose sum will be outside the range `-$n`

to `+$n`

, and the
negation of that will always be unique with respect to the
numbers already selected.

#!/usr/bin/perl use v5.26; # The Weekly Challenge - 2024-01-15 use utf8; # Week 252 task 2 - Unique sum zero use strict; # Peter Campbell Smith use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge binmode STDOUT, ':utf8'; unique_sum_zero(1); unique_sum_zero(5); unique_sum_zero(50); sub unique_sum_zero { my ($n, $method, $sum, $j, @array, %used); $n = shift @_; say qq[\nInput: \$n = $n]; # try two ways for $method (1 .. 2) { @array = (); # use -n to +n, including 0 in the middle if an odd number if ($method == 1) { push @array, 0 if $n & 1; for $j (1 .. int($n / 2)) { push @array, -$j; unshift @array, $j } # choose $n - 1 random numbers and add - $sum - unless it has already been used } elsif ($method == 2) { while (1) { $sum = 0; @array = (); %used = (); # fill @array with $n - 1 random integers from the range -$n to +$n while (@array < $n - 1) { $j = int(rand($n * 2)) - $n; next if $used{$j}; $used{$j} = 1; push @array, $j; $sum += $j; } # add the negated sum unless it has been used already push @array, -$sum; last unless $used{-$sum}; } } # show result $sum = 0; $sum += $array[$_] for 0 .. $n - 1; say qq[Output: (] . join(', ', @array) . qq[), \$sum = $sum]; } }

Input: $n = 1 Output: (0), $sum = 0 Output: (0), $sum = 0 Input: $n = 5 Output: (2, 1, 0, -1, -2), $sum = 0 Output: (-3, 2, 4, -4, 1), $sum = 0 Input: $n = 50 Output: (25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -20, -21, -22, -23, -24, -25), $sum = 0 Output: (42, -37, 28, -5, 8, -4, 2, -12, 39, -8, 41, 32, -27, 43, 15, -17, 29, -3, -47, -28, 1, 38, -25, 30, 26, 20, -24 , -43, -10, 19, -21, 6, -11, 35, -34, -42, -46, 37, -14, 25, -36, 21, -41, -33, -26, -9, -38, 12, -29, 121), $sum = 0

Peter Campbell Smith is hereby placed in the public domain