Counts and discounts
Weekly challenge 325 — 9 June 2025
Week 325: 9 Jun 2025
You are given an array containing only 0s and 1s. Write a script to find out the maximum consecutive 1s in the given array.
Example 1 Input: @binary = (0, 1, 1, 0, 1, 1, 1) Output: 3 Example 2 Input: @binary = (0, 0, 0, 0) Output: 0 Example 3 Input: @binary = (1, 0, 1, 0, 1, 1) Output: 2
The simplest solution to this is to pass once along the array,
incrementing $this_run
when a 1 is encountered, and when a
zero is found setting $max_run
to $this_run
and $this_run
to zero.
This will give the wrong answer if the longest run of 1s finishes with the last element of the array, but that is easily fixed by pushing a 0 onto the end of the array at the start.
I tried that algorithm with a million random 0s and 1s and it produced the result (20) in under 2 seconds so I think that's good enough.
There is one possible optimisation, which is that if
the current element is zero and
$max_run
equals or exceeds the number of elements of
@array
still to be inspected, you can drop out of the
loop because there cannot be a yet-undiscovered longer
run. However, in most cases the cost of an extra if
for such cases
will negate the peformance gain.
#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.26; # The Weekly Challenge - 2025-06-09 use utf8; # Week 325 - task 1 - Consecutive ones use warnings; # Peter Campbell Smith binmode STDOUT, ':utf8'; use Encode; consecutive_ones(0, 1, 1, 0, 1, 1, 1); consecutive_ones(0, 0, 0, 0); consecutive_ones(1, 0, 1, 0, 1, 1); # bigger example my @array; push @array, int(rand($_)) & 1 for 0 .. 100; consecutive_ones(@array); sub consecutive_ones { my(@array, $this_run, $max_run, $j); # initialise @array = @_; push @array, 0; $max_run = $this_run = 0; # explore array for $j (@array) { # it's a 1 if ($j) { $this_run ++; $max_run = $this_run if $this_run > $max_run; # it's a 0 } else { $this_run = 0; } } say qq[\nInput: (] . join(', ', @array[0 .. $#array - 1]) . q[)]; say qq[Output: $max_run]; }
Input: (0, 1, 1, 0, 1, 1, 1) Output: 3 Input: (0, 0, 0, 0) Output: 0 Input: (1, 0, 1, 0, 1, 1) Output: 2 Input: (0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0) Output: 5
Any content of this website which has been created by Peter Campbell Smith is in the public domain