The weekly challenge 271 - Task 1: Maximum Ones

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-271/#TASK1
 3 #
 4 # Task 1: Maximum Ones
 5 # ====================
 6 #
 7 # You are given a m x n binary matrix.
 8 #
 9 # Write a script to return the row number containing maximum ones, in case of
10 # more than one rows then return smallest row number.
11 #
12 ## Example 1
13 ##
14 ## Input: $matrix = [ [0, 1],
15 ##                    [1, 0],
16 ##                  ]
17 ## Output: 1
18 ##
19 ## Row 1 and Row 2 have the same number of ones, so return row 1.
20 #
21 ## Example 2
22 ##
23 ## Input: $matrix = [ [0, 0, 0],
24 ##                    [1, 0, 1],
25 ##                  ]
26 ## Output: 2
27 ##
28 ## Row 2 has the maximum ones, so return row 2.
29 #
30 ## Example 3
31 ##
32 ## Input: $matrix = [ [0, 0],
33 ##                    [1, 1],
34 ##                    [0, 0],
35 ##                  ]
36 ## Output: 2
37 ##
38 ## Row 2 have the maximum ones, so return row 2.
39 #
40 ############################################################
41 ##
42 ## discussion
43 ##
44 ############################################################
45 #
46 # We walk the matrix row by row. If the number of 1s is higher
47 # than the previous maximum we have both a new maximum and the
48 # new index of this maximum. In the end, return the index.
49 
50 use strict;
51 use warnings;
52 
53 maximum_ones( [ [0, 1], [1, 0] ] );
54 maximum_ones( [ [0, 0, 0], [1, 0, 1] ] );
55 maximum_ones( [ [0, 0], [1, 1], [0, 0] ] );
56 
57 sub maximum_ones {
58    my $matrix = shift;
59    print "Input: [\n";
60    foreach my $row (@$matrix) {
61       print "         [", join(", ", @$row), "],\n";
62    }
63    print "       ]\n";
64    my $max_ones = 0;
65    my $max_index = 1;
66    my $index = 0;
67    foreach my $row (@$matrix) {
68       $index++;
69       my $count = 0;
70       foreach my $elem (@$row) {
71          $count++ if $elem == 1;
72       }
73       if($count > $max_ones) {
74          $max_index = $index;
75          $max_ones = $count;
76       }
77    }
78    print "Output: $max_ones\n";
79 }