The weekly challenge 391 - Task 1: Array Median

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-391/#TASK1
  3 #
  4 # Task 1: Array Median
  5 # ====================
  6 #
  7 # You are given two sorted arrays.
  8 #
  9 # Write a script to merge the two given sorted arrays and return the median of
 10 # the merged array.
 11 #
 12 ## Example 1
 13 ##
 14 ## Input: @arr1 = (2), @arr2 = (4)
 15 ## Output: 3.0
 16 ##
 17 ## Merged array: (2,4)
 18 ## Median: (2+4)/2 => 3
 19 #
 20 ## Example 2
 21 ##
 22 ## Input: @arr1 = (1,2,3), @arr2 = (7,8,9,10)
 23 ## Output: 7.0
 24 ##
 25 ## Merged array: (1,2,3,7,8,9,10)
 26 ## Length of merged array is 7, the 4th element is 7.
 27 #
 28 ## Example 3
 29 ##
 30 ## Input: @arr1 = (), @arr2 = (10,20,30,40)
 31 ## Output: 25.0
 32 ##
 33 ## Merged array: (10,20,30,40)
 34 ## Median: (20+30)/2 => 25
 35 #
 36 ## Example 4
 37 ##
 38 ## Input: @arr1 = (100), @arr2 = (1,2,3,4,5,6,7)
 39 ## Output: 4.5
 40 ##
 41 ## Merged array: (1,2,3,4,5,6,7,100)
 42 ## Median: (4+5)/2 => 4.5
 43 #
 44 ## Example 5
 45 ##
 46 ## Input: @arr1 = (1,2,2), @arr2 = (2,2,3)
 47 ## Output: 2.0
 48 ##
 49 ## Merged array: (1,2,2,2,2,3)
 50 ## Median: (2+2)/2 => 2
 51 #
 52 ############################################################
 53 ##
 54 ## discussion
 55 ##
 56 ############################################################
 57 #
 58 # First we merge the arrays by picking the smaller element at the
 59 # beginning of each array until one of the arrays is empty, then
 60 # we add the remaining elements from the other array. Since the
 61 # input arrays are sorted, that new list will also be sorted.
 62 # Then we calculated the median (middle element in case of an odd
 63 # number of elements, and the average of the two middle elements
 64 # in case of an even amount of elements).
 65 
 66 use v5.36;
 67 
 68 sub array_median($arr1, $arr2) {
 69     say "Input: [" . join(", ", @$arr1) . "], [" . join(", ", @$arr2) . "]";
 70     my @merged = ();
 71     while(scalar(@$arr1) and scalar(@$arr2)) {
 72         my $l = $arr1->[0];
 73         my $r = $arr2->[0];
 74         if($l < $r) {
 75             push @merged, $l;
 76             shift @$arr1;
 77         } else {
 78             push @merged, $r;
 79             shift @$arr2;
 80         }
 81     }
 82     if(scalar(@$arr1)) {
 83         push @merged, @$arr1;
 84     }
 85     if(scalar(@$arr2)) {
 86         push @merged, @$arr2;
 87     }
 88     my $elems = scalar(@merged);
 89     if($elems % 2) {
 90         say "Output: " . $merged[int($elems/2)];
 91     } else {
 92         my $tmp = int($elems/2);
 93         say "Output: " . (($merged[$tmp-1] + $merged[$tmp]) / 2);
 94     }
 95 }
 96 
 97 
 98 array_median([2], [4]);
 99 array_median([1,2,3], [7,8,9,10]);
100 array_median([], [10,20,30,40]);
101 array_median([100], [1,2,3,4,5,6,7]);
102 array_median([1,2,2], [2,2,3]);