The Weekly Challenge 074

Majority Element and FNR Character

Solutions on GitHub

Task 1: Majority Element

You are given an array of integers @A. Write a script to find the majority element in the list, defined as an element that appears more than floor(size / 2) times. If no such element exists, return -1.

Example Output

Input: @A = (1, 2, 2, 3, 2, 4, 2) Output: 2 Input: @A = (1, 3, 1, 2, 4, 5) Output: -1

Logic

Compute the threshold floor(length / 2). Count the frequencies of each element in the array. If any element's count strictly exceeds the threshold, return that element immediately. If no element qualifies after traversing the list, return -1.

Perl Solution

ch-1.pl

sub get_majority_element ($arr) { return -1 if !@$arr; my %counts; my $threshold = int( scalar(@$arr) / 2 ); for my $val (@$arr) { $counts{$val}++; return $val if $counts{$val} > $threshold; } return -1; }

Python Solution

ch-1.py

def get_majority_element(arr: list[int]) -> int: """Return majority element appearing more than len(arr)//2 times, or -1.""" if not arr: return -1 counts: dict[int, int] = {} threshold = len(arr) // 2 for item in arr: counts[item] = counts.get(item, 0) + 1 if counts[item] > threshold: return item return -1

Task 2: FNR Character

You are given a string $S. Write a script to print the series of first non-repeating characters (or # if none) dynamically as characters from the string are processed one by one.

Example Output

Input: $S = "ababc" Output: "abb#c" Input: $S = "xyzzyx" Output: "xyzyx#"

Logic

Maintain a count dictionary and an ordered queue of characters that currently have an occurrence count of 1. As each character arrives, update its frequency count. If it is seen for the first time, append it to the queue; if seen again, remove it from the queue. At each step, the last element in the queue is the current first non-repeating character (or # if the queue is empty).

Perl Solution

ch-2.pl

sub get_fnr ($input) { return '' if !defined $input || length($input) == 0; my %fnr_count; my @fnr_queue; my $result = ''; for my $char ( split //, $input ) { $fnr_count{$char}++; if ( $fnr_count{$char} == 1 ) { push @fnr_queue, $char; } else { my $pos; for my $i ( 0 .. $#fnr_queue ) { if ( $fnr_queue[$i] eq $char ) { $pos = $i; last; } } splice @fnr_queue, $pos, 1 if defined $pos; } $result .= @fnr_queue ? $fnr_queue[-1] : '#'; } return $result; }

Python Solution

ch-2.py

def get_fnr(in_str: str) -> str: """Find and return the FNR sequence for the given input string.""" fnr_count: dict[str, int] = {} fnr_queue: list[str] = [] result = [] for char in in_str: fnr_count[char] = fnr_count.get(char, 0) + 1 if fnr_count[char] == 1: fnr_queue.append(char) elif char in fnr_queue: fnr_queue.remove(char) result.append(fnr_queue[-1] if fnr_queue else "#") return "".join(result)