The weekly challenge 226 - Task 2: Zero Array

  1 #!/usr/bin/perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-226/#TASK2
  3 #
  4 # Task 2: Zero Array
  5 # ==================
  6 #
  7 # You are given an array of non-negative integers, @ints.
  8 #
  9 # Write a script to return the minimum number of operations to make every
 10 # element equal zero.
 11 #
 12 ## In each operation, you are required to pick a positive number less than or
 13 ## equal to the smallest element in the array, then subtract that from each
 14 ## positive element in the array.
 15 #
 16 #
 17 # Example 1:
 18 #
 19 # Input: @ints = (1, 5, 0, 3, 5)
 20 # Output: 3
 21 #
 22 # operation 1: pick 1 => (0, 4, 0, 2, 4)
 23 # operation 2: pick 2 => (0, 2, 0, 0, 2)
 24 # operation 3: pick 2 => (0, 0, 0, 0, 0)
 25 #
 26 # Example 2:
 27 #
 28 # Input: @ints = (0)
 29 # Output: 0
 30 #
 31 # Example 3:
 32 #
 33 # Input: @ints = (2, 1, 4, 0, 3)
 34 # Output: 4
 35 #
 36 # operation 1: pick 1 => (1, 0, 3, 0, 2)
 37 # operation 2: pick 1 => (0, 0, 2, 0, 1)
 38 # operation 3: pick 1 => (0, 0, 1, 0, 0)
 39 # operation 4: pick 1 => (0, 0, 0, 0, 0)
 40 #
 41 ############################################################
 42 ##
 43 ## discussion
 44 ##
 45 ############################################################
 46 #
 47 # Comment:
 48 # While the description says "pick a positive number less than or
 49 # equal to the smallest element in the array", it is actually the
 50 # smallest *positive* element in the array, or we could only pick
 51 # "0" after the first element in the array is 0.
 52 #
 53 # Let's think a moment. If we pick any number that is less than
 54 # the smallest positive number, we will have to pick another
 55 # number again to get the smallest positive number to zero, so
 56 # it's always best to use the smallest positive number to minimize
 57 # the number of picks. Given this, it's simple to always pick the
 58 # smallest positive number, substract it from all remaining
 59 # positive numbers and be done.
 60 
 61 use strict;
 62 use warnings;
 63 
 64 zero_array(1, 5, 0, 3, 5);
 65 zero_array(0);
 66 zero_array(2, 1, 4, 0, 3);
 67 
 68 sub zero_array {
 69    my @ints = @_;
 70    print "Input: (" . join(", ", @ints) . ")\n";
 71    my $steps = 0;
 72    while(non_zero(@ints)) {
 73       my $smallest_positive = smallest_positive(@ints);
 74       # substract the smallest positive number from each non-zero element
 75       @ints = map { $_ == 0 ? 0 : $_ - $smallest_positive; } @ints;
 76       $steps++;
 77    }
 78    print "Output: $steps\n";
 79 }
 80 
 81 # check if there are non-zero elements in an array
 82 sub non_zero {
 83    my @ints = @_;
 84    foreach my $i (@ints) {
 85       return 1 if $i;
 86    }
 87    return 0;
 88 }
 89 
 90 # find the smallest positive number in an array
 91 sub smallest_positive {
 92    my @ints = @_;
 93    my $smallest;
 94    foreach my $i (@ints) {
 95       if($i) {
 96          $smallest //= $i;
 97          $smallest = $i if $i < $smallest;
 98       }
 99    }
100    # returns undef if there is no positive number in the array
101    return $smallest;
102 }