Absent smallest positive

You are given an array of integers. Write a script to return the smallest absent positive integer such that it is strictly greater than the average of all elements in the given array.

Examples

Example 1
Input: @arr = (1, 2, 4, 5, 6)
Output: 7
Average: (1 + 2 + 4 + 5 + 6) / 5 = 3.6
We need the smallest positive integer absent from nums that is
   strictly greater than 3.6.
The positive integers greater than 3.6 are 4, 5, 6, 7, ....
4 is in the given array.
5 is in the given array.
6 is in the given array.
7 is not in.

Example 2
Input: @arr = (-5, -2, -1, 3)
Output: 1
Average: (-5 -2 -1 + 3) / 4 = -1.25
We need the smallest absent positive integer strictly greater than
   -1.25.
Positive integers are 1, 2, 3, 4, ... (all are strictly greater than
   -1.25).
1 is positive and absent from the given array.

Example 3
Input: @arr = (1, 2, 3)
Output: 4
Average: (1 + 2 + 3) / 3 = 2.0
We need an integer strictly greater than 2.0.
3 is in the given array.
4 is not in.

Example 4
Input: @arr = (2, 3, 7, 8)
Output: 6
Average: (2 + 3 + 7 + 8) / 4 = 5.0
We need an integer strictly greater than 5.0.
6 is not in the given array.

Example 5
Input: @arr = (1, 1, 1, 10)
Output: 4
Average: (1 + 1 + 1 + 10) / 4 = 3.25
Positive integers strictly greater than 3.25: 4, 5, 6, ...
4 is not in the given array.

Analysis

Perhaps my mind has been dulled by the clocks going back, but I couldn't think of a shortcut to the obvious stepwise solution.

First I go through the array, summing the numbers and recording their presence in %present - a hash rather than an array as some of the numbers may be negative.

Then I start with the smallest integer which is larger than the average and no less than 1 and increment that until it doesn't appear in %present.

And that's the answer. It only takes 2 seconds to handle an array of a million numbers.

Peter has published a blog post on Perl Weekly Challenge 397 which summarises the Perl solution he used which employs a hash lookup to manage a process efficiently for positive and negative integers. The code is built in 11 lines and runs efficiently for large arrays.

This review may cover either or both challenges for this week.

Try it 

Your input:

#!/usr/bin/perl

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

use v5.28;    # The Weekly Challenge - 2026-10-26
use utf8;     # Week 397 - task 1 - Absent smallest positive
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

absent_smallest_positive(1, 2, 4, 5, 6);
absent_smallest_positive(-5, -2, -1, 3);
absent_smallest_positive(1, 2, 3);
absent_smallest_positive(2, 3, 7, 8);
absent_smallest_positive(1, 1, 1, 10);

my @array;
push @array, int(rand(10000)) for 1 .. 500;
absent_smallest_positive(@array);

sub absent_smallest_positive {
    
    my (@array, $total, %present, $answer);
    
    # find total and record presence
    @array = @_;
    for (@array) {
        $total += $_;
        $present{$_} = 1;
    }
    
    # find minimum answer and increment until not present
    $answer = int($total / $#array) + 1;
    $answer = 1 if $answer < 1;
    $answer ++ while $present{$answer};
    
    # report
    say qq[\nInput:  (] . join(', ', @array) . ')';
    say qq[Output: $answer];
}

11 lines of code

Output from script

Input:  (1, 2, 4, 5, 6)
Output: 7

Input:  (-5, -2, -1, 3)
Output: 1

Input:  (1, 2, 3)
Output: 4

Input:  (2, 3, 7, 8)
Output: 9

Input:  (1, 1, 1, 10)
Output: 5

Input:  (9666, 5416, 1918, 2300, 8750, 5620, 6396, 933, 2782, 2295,
   567, 1023, 5617, 5044, 8860, 4595, 4675, 4812, 597, 8533, 9402,
   2178, 5788, 829, 4709, 3471, 7122, 3586, 5760, 8240, 9426, 2788,
   1774, 9609, 2921, 7624, 9193, 1822, 9292, 9028, 4058, 3297, 4170,
   6681, 1087, 5257, 7553, 1198, 2344, 4793, 5786, 7455, 1851, 1354,
   8046, 1562, 7684, 9239, 4149, 7005, 9490, 7911, 3543, 796, 4522,
   1598, 1566, 2623, 7922, 9846, 4456, 5071, 4592, 9037, 9861, 878,
   8402, 9160, 2283, 226, 5256, 911, 209, 2577, 6535, 1069, 2785, 34,
   8328, 2291, 2486, 3430, 5509, 575, 7160, 4978, 1905, 5622, 244,
   8588, 3460, 7517, 4257, 7769, 8217, 6456, 6727, 2898, 9128, 9720,
   3280, 1905, 5120, 3485, 3273, 7717, 5358, 3240, 4368, 9977, 7462,
   107, 3917, 9431, 4419, 5887, 3914, 9132, 7289, 4620, 9024, 4443,
   2591, 5240, 2593, 2146, 8612, 8822, 6406, 332, 4025, 5185, 6643,
   3883, 3277, 240, 516, 3118, 5490, 5620, 7193, 4569, 9397, 1534,
   9032, 6141, 4303, 8451, 8125, 3278, 2735, 1712, 1436, 6910, 1452,
   9244, 312, 7298, 4453, 7699, 6032, 4483, 761, 7961, 8942, 5632,
   5738, 1554, 267, 1407, 2752, 4123, 1056, 7799, 929, 8146, 4169,
   1085, 8843, 1411, 2469, 2294, 5999, 468, 8263, 3526, 7455, 4240,
   6762, 2613, 8500, 4941, 5433, 9882, 8689, 4160, 4208, 2573, 8420,
   7005, 821, 8920, 8314, 7071, 5137, 6804, 6777, 8135, 5116, 6625,
   5010, 3195, 536, 6778, 248, 8974, 4338, 3514, 7023, 494, 2473,
   7478, 5636, 9733, 3584, 2901, 5699, 8805, 8308, 4927, 7573, 8194,
   3109, 7368, 3725, 6344, 5626, 184, 6467, 7746, 2574, 9992, 5325,
   2434, 9266, 1143, 1454, 2678, 3349, 1501, 4148, 314, 7966, 9455,
   4847, 5670, 9326, 4465, 2134, 1701, 5694, 6298, 403, 2870, 3891,
   861, 9252, 450, 1977, 7300, 7659, 5249, 4376, 9931, 9688, 6042,
   6268, 3931, 8498, 1025, 5656, 9094, 4774, 8952, 3712, 5937, 147,
   2871, 1335, 1871, 6784, 8976, 3544, 6978, 892, 5333, 4441, 3281,
   548, 4511, 6802, 3536, 925, 2450, 9460, 4946, 1778, 5454, 7028,
   5363, 953, 2893, 4111, 9303, 1992, 4919, 6202, 4283, 5453, 139,
   2354, 4709, 9946, 5275, 8280, 6978, 5815, 8136, 9756, 1005, 8632,
   2158, 4386, 6546, 968, 8742, 8603, 8136, 5025, 6039, 6989, 7102,
   9581, 5802, 2889, 8815, 7060, 4715, 5166, 5424, 8404, 2153, 2679,
   9877, 8553, 1627, 9472, 3786, 5948, 67, 3256, 5986, 8197, 4340,
   2850, 8480, 9285, 2696, 6917, 3650, 3151, 4667, 3530, 9256, 4507,
   3924, 4322, 3124, 1248, 6970, 6919, 5946, 8118, 6702, 7907, 703,
   8377, 3974, 6125, 9858, 7472, 5425, 2008, 4175, 9235, 55, 4931,
   9177, 3278, 6186, 3094, 9728, 280, 444, 2807, 9600, 6104, 9875,
   8750, 9509, 3489, 1005, 8837, 3659, 1904, 6963, 5937, 5174, 8299,
   7361, 344, 4823, 8578, 9588, 7445, 4305, 6980, 3986, 2408, 5345,
   6811, 6063, 416, 3351, 5621, 3615, 6497, 29, 3563, 5302, 2367,
   2862, 8870, 4799, 9973, 1628, 5917, 3805, 8234, 8251, 1653, 792,
   3390, 7429, 6258, 5860, 6601, 2023, 5177, 6054, 9154, 710, 7211,
   8355, 4519, 1492, 7720, 7623, 3411, 5229, 6160, 5252, 8090, 9372,
   2924, 7379, 2800, 5692, 4751, 3149, 346, 3303, 9637, 7756, 9108,
   2203, 8300, 8620, 8848, 4367)
Output: 5121