Peter
Peter Campbell Smith

Special and unique numbers

Weekly challenge 252 — 15 January 2024

Week 252: 15 Jan 2024

Task 2

Task — Unique sum zero

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

Examples


Example 1
Input: $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 2
Input: $n = 3
Output: (-1, 0, 1)

Example 3
Input: $n = 1
Output: (0)

Analysis

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.

Try it 

Try running the script with any input:



example: 10

Script


#!/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];
    }   
}

Output


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

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain