Task 1: 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 are more than one then return the largest.
A lucky integer is an integer that has a frequency in the array equal to its value.
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
Method Explanation
Finding the lucky integer is a classic frequency-counting problem that can be solved in $O(N)$ time and $O(U)$ space (where $U$ is the number of unique integers in the input array):
- First, iterate through the input array and build a frequency map (hash table / dictionary) mapping each integer $x$ to its occurrence count $f(x)$.
- Filter the distinct keys to find all integers satisfying $x = f(x)$.
- If one or more lucky integers exist, return their maximum value; otherwise return $-1$.
Perl Solution
use v5.38;
use warnings;
use List::Util qw(max);
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);
signature_for find_lucky_integer => (
method => 0,
positional => [ ArrayRef [Int] ],
);
sub find_lucky_integer ($ints_ref) {
my %freq;
for my $num (@$ints_ref) {
$freq{$num}++;
}
my @lucky_integers;
for my $num ( keys %freq ) {
if ( $num == $freq{$num} ) {
push @lucky_integers, int($num);
}
}
if (@lucky_integers) {
return max(@lucky_integers);
}
return -1;
}
Python Solution
from collections import Counter
def find_lucky_integer(ints: list[int]) -> int:
"""Find the lucky integer in the given list of integers."""
freq = Counter(ints)
lucky_integers = [num for num, count in freq.items() if num == count]
if lucky_integers:
return max(lucky_integers)
return -1