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.

Task analysis is well drafted to keep you engaged. Ofcourse you have the DIY tool to play as well.

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

Try it 

Try running the script with any input:

Your @ints =

example: 1, 2, 3, 4, 3, 5, 3

⤡

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

11 lines of code

Output from script

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