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.

Try it 

Your input:

#!/usr/bin/perl

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

use v5.26;    # 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];
}

19 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:  (4097, 4952, 5796, 1504, 4308, 277, 3573, 179, 4407, 1196,
   6300, 1972, 7009, 5510, 7401, 1644, 9478, 169, 6704, 8798, 1073,
   8893, 5823, 1385, 309, 8165, 9343, 3390, 2648, 3879, 6829, 5458,
   9941, 8911, 5752, 9992, 5723, 4688, 8075, 9142, 9944, 3804, 7874,
   3682, 4391, 2515, 5237, 8230, 5436, 715, 3863, 7545, 4205, 7118,
   8992, 5136, 9475, 1024, 6286, 8458, 4968, 1164, 5255, 294, 7902,
   1908, 7047, 8055, 8270, 7209, 1859, 7829, 9954, 1062, 6450, 7873,
   3134, 7507, 4957, 3330, 8323, 4024, 3499, 5395, 2238, 4981, 182,
   700, 4703, 57, 720, 818, 9379, 9638, 6778, 4535, 3330, 1141, 9602,
   2680, 6051, 8470, 7787, 4232, 5562, 55, 2083, 4210, 1315, 8440,
   5727, 6143, 3081, 7752, 9423, 1236, 4527, 1573, 1131, 471, 5983,
   7266, 2269, 6799, 4874, 8322, 843, 331, 4702, 1259, 4764, 7232,
   5173, 429, 4008, 1414, 1495, 2951, 1129, 9413, 9959, 7304, 6330,
   2044, 8032, 5706, 5328, 9129, 9445, 577, 7360, 5041, 546, 4771,
   3116, 6039, 1671, 9935, 1331, 4800, 2932, 5838, 1093, 1628, 4851,
   9616, 9368, 5257, 1222, 8959, 9188, 2669, 747, 8995, 9773, 6979,
   9921, 3099, 1447, 4269, 7761, 2585, 3538, 4559, 1859, 6165, 4940,
   3320, 9343, 4485, 4231, 8670, 8388, 7661, 8152, 5347, 9322, 9795,
   4963, 686, 6050, 6328, 8304, 5138, 797, 864, 272, 1592, 9147, 3093,
   1728, 4310, 9349, 9345, 7467, 1075, 5060, 414, 2622, 7007, 4500,
   6016, 193, 7139, 591, 2770, 3302, 8305, 5586, 9036, 6819, 1376,
   3154, 9392, 3420, 8572, 9511, 7925, 7629, 81, 191, 9622, 6509,
   1032, 8208, 4917, 7711, 6852, 3844, 3283, 9704, 9089, 3050, 7526,
   6965, 7969, 5622, 3322, 6511, 4574, 1961, 6198, 4708, 7924, 7566,
   5641, 3092, 8027, 2497, 8724, 3983, 8774, 2243, 1520, 5701, 7363,
   807, 8736, 9848, 3662, 3794, 1314, 610, 1817, 2033, 9042, 6718,
   1804, 6218, 4223, 8168, 3953, 2467, 1838, 2097, 9513, 3096, 7841,
   9465, 3683, 7558, 6879, 7945, 9436, 5017, 2921, 7486, 4753, 2748,
   5601, 6360, 8051, 7149, 3334, 4621, 5950, 6016, 3865, 3248, 9710,
   9562, 8558, 4906, 6396, 2021, 8518, 2226, 4037, 7206, 6191, 2497,
   6759, 7755, 3274, 1125, 2304, 4771, 4961, 7512, 5899, 8753, 7570,
   5159, 7586, 4033, 4508, 6606, 5593, 3068, 7979, 4061, 2953, 7770,
   6808, 8426, 4284, 7458, 5541, 5323, 1715, 4828, 5517, 3452, 4533,
   6534, 3930, 2028, 3840, 5512, 3762, 3606, 7820, 966, 2772, 1736,
   3078, 5113, 7928, 9517, 4651, 5299, 7619, 2343, 9991, 6078, 4852,
   2342, 7554, 9373, 3090, 1950, 7170, 6126, 2505, 2643, 9467, 9930,
   8527, 2344, 4225, 406, 9709, 988, 287, 580, 6132, 9952, 1780, 710,
   8741, 3640, 9870, 8972, 8, 3814, 5697, 3714, 5766, 2022, 6676,
   9777, 789, 7482, 4999, 3205, 7976, 6437, 7426, 840, 4602, 614,
   9563, 8373, 3012, 2995, 4602, 7780, 7009, 6460, 6560, 1360, 5817,
   7597, 5486, 9186, 2254, 3459, 7815, 2477, 406, 2440, 8489, 581,
   5669, 2721, 3804, 763, 9199, 8515, 3, 361, 2400, 8284, 3825, 889,
   560, 2314, 7728, 5012, 8753, 3754, 6056, 4808, 5956, 6117, 4479,
   4123, 3417, 7151, 5633, 8001, 1777, 9041, 9874, 7896, 4560, 5635,
   3711, 5691, 7239, 391, 5949, 1203, 5397, 3136, 5515, 3974, 9064,
   7725, 6773)
Output: 5125