Number of 1s in a sorted array

Problem

Count number of 1s in a sorted array.

e.g. [1,1,1,1,0,0,0,0,0,0]

Code

def countOneBS(row, start, end):
        if row[start] == 0:
            return 0
        
        if row[end] == 1:
            return end - start + 1
        
        # The mid is dependent on the index of start
        mid = start + (end - start) // 2
        # print("mid=", mid, "start=", start, "end=", end)
        return countOneBS(row, start, mid) + countOneBS(row, mid + 1, end)
    
l = [1,1,1,0,0,0]

print(countOneBS(l, 0, len(l) - 1))

Reference

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: