Number of 1s in a sorted array


Count number of 1s in a sorted array.

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


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))


Leave a Reply

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

You are commenting using your 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: