Task 1: 33% Appearance
You are given an array of integers, @ints.
Write a script to find an integer that appears 33% or more of the time in the given array.
If there is more than one such integer, return the smallest one. If no such integer exists, return undef / None.
Example 1: Input: @ints = (1, 2, 3, 3, 3, 3, 4, 2) → Output: 3
Example 2: Input: @ints = (1, 1) → Output: 1
Example 3: Input: @ints = (1, 2, 3) → Output: 1
Method Explanation
The problem requires identifying any integer whose appearance rate in an array meets or exceeds 33% (i.e. $\text{count} / n \ge 0.33$). In case multiple numbers satisfy this criterion, we must choose the smallest integer.
Our approach is straightforward:
- If the array is empty, return
undef(orNone). - Compute frequency counts for every number using a hash table in Perl or a
Counterin Python. - Filter the candidates whose relative frequency meets or exceeds 33% ($\ge 0.33$).
- If any candidates qualify, return the minimum integer; otherwise return
undef/None.
This approach runs in $O(N)$ time to count occurrences, followed by sorting or finding the minimum among at most three candidates (since at most 3 distinct numbers can each appear ≥ 33% of the time). Memory usage is $O(U)$ where $U$ is the number of distinct integers in the array.
Perl Solution
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);
signature_for find_integer_appearing_33_percent_or_more => (
method => 0,
positional => [ ArrayRef [Int] ],
);
sub find_integer_appearing_33_percent_or_more ($ints) {
return unless @$ints;
my $n = scalar @$ints;
my %count;
$count{$_}++ for @$ints;
my @valid_numbers = grep { ( $count{$_} / $n ) >= 0.33 } keys %count;
return unless @valid_numbers;
@valid_numbers = sort { $a <=> $b } @valid_numbers;
return $valid_numbers[0];
}
Python Solution
from collections import Counter
def find_integer_appearing_33_percent_or_more(ints: list[int]) -> int | None:
"""Find an integer that appears 33% or more of the time in the given list."""
if not ints:
return None
counts = Counter(ints)
n = len(ints)
valid_numbers = [num for num, cnt in counts.items() if (cnt / n) >= 0.33]
return min(valid_numbers) if valid_numbers else None