Camel
Peter
Peter Campbell Smith

Counts and discounts

Weekly challenge 325 — 9 June 2025

Week 325: 9 Jun 2025

Task 1

Task — Consecutive ones

You are given an array containing only 0s and 1s. Write a script to find out the maximum consecutive 1s in the given array.

Examples


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

Analysis

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.

Try it 

Try running the script with any input:



example: 1, 1, 0, 0, 1, 1, 1, 0, 0, 0

Script


#!/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];
}

Output


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