Task — Lucky integer

You are given an array of integers, @ints. Write a script to find the lucky integer if found, otherwise return -1. If there is more than one then return the largest. A lucky integer is an integer that has a frequency in the array equal to its value.

Examples

Example 1
Input: @ints = (2, 2, 3, 4)
Output: 2

Example 2
Input: @ints = (1, 2, 2, 3, 3, 3)
Output: 3

Example 3
Input: @ints = (1, 1, 1, 3)
Output: -1

Analysis

This challenge at first appears easy. First calculate the frequencies $freq{$e}, then loop over the keys of %freq in reverse order (ie largest first), and the first one where $freq{$e} == $e is the desired answer:

$freq{$_} ++ for @ints;
	
for $e (reverse sort keys %freq) {
   if ($e == $freq{$e}) {
      say qq[Output: $e];
      return;
   }
}
say qq[Output: -1];

But there is a snag with that solution, which is that the keys of a hash are treated as strings. That means, for example, that 3 is treated as being larger than 20, so the example in my solution of 3 3s followed by 20 20s comes up with the wrong answer.

Another possibility is to use an array instead of a hash to hold the frequencies. But that has an issue in that the array may be sparse: for example 1, 1, 1, 3, 3, 3. Here $freq[2] is undefined, which creates a warning under use warn unless a messy solution like defined($freq[$int]) ? $freq[$int] : 0 is used.

So I stuck with the hash version, but for safety added a large number (1e6) to the keys. Those will sort correctly since 1000003 is less than 1000020 whether they are treated as strings or numbers.

I also pondered the issue of negative numbers, which are not excluded in the task definition. Of course they can never be the correct answer, as -2 can never appear minus twice, but if they are present, my solution handles them correctly. An array-based frequency count would fall over with negative indices.

Lastly there is the case of an empty array, where arguably the correct output is 0, since it appears 0 times. However, I decided against special-casing that, so my algorithm returns -1 in that case.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2024-08-26
use utf8;     # Week 284 - task 1 - Lucky integer
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

lucky_integer(2, 2, 3, 4);
lucky_integer(1, 2, 2, 3, 3, 3);
lucky_integer(1, 1, 1, 3);
lucky_integer(3, 3, 3, 20, 20, 20, 20, 20, 20, 20, 20, 20,
    20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20);
lucky_integer(-1, -2, 0, 1, 1, 2, 2, 2, 3, 3, 3);
lucky_integer(-2, -2, -3, -3, -3);

my @ints;
for (1 .. 50) {
    push @ints, int(rand(20)) + 1;
}
lucky_integer(@ints);

sub lucky_integer {
    
    my (@ints, %freq, $j, $e, $big);
    
    @ints = @_;
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . ')';
    
    # calculate frequencies
    $big = 1e6;
    $freq{$_ + $big} ++ for @ints;
    
    # find the largest lucky one
    for $e (reverse sort keys %freq) {
        if ($e - $big == $freq{$e}) {
            say qq[Output: ] . ($e - $big);
            return;
        }
    }
    
    # or they are all unlucky
    say qq[Output: -1];
}

Output

Input:  @ints = (2, 2, 3, 4)
Output: 2

Input:  @ints = (1, 2, 2, 3, 3, 3)
Output: 3

Input:  @ints = (1, 1, 1, 3)
Output: -1

Input:  @ints = (3, 3, 3, 20, 20, 20, 20, 20, 20, 20, 20,
   20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20)
Output: 20

Input:  @ints = (-1, -2, 0, 1, 1, 2, 2, 2, 3, 3, 3)
Output: 3

Input:  @ints = (-2, -2, -3, -3, -3)
Output: -1

Input:  @ints = (13, 4, 19, 8, 11, 16, 9, 10, 16, 18, 15,
   4, 19, 16, 7, 17, 3, 14, 14, 3, 10, 1, 10, 14, 6, 3, 4,
   8, 12, 6, 4, 16, 18, 13, 13, 4, 16, 12, 6, 18, 3, 20,
   20, 9, 15, 6, 19, 8, 10, 4)
Output: 1