Ones Outnumber Zeros

Medium

You are given an array bits holding only 0s and 1s. Count the contiguous stretches in which 1s **strictly outnumber** 0s. Stretches with different boundaries count separately. The answer can be large, so return it modulo 10⁹ + 7. Trying every stretch is O(n²); look for something faster.

Example 1

bits=[1, 0, 1, 1] → 7

The three single 1s, [1, 1], [0, 1, 1], [1, 0, 1] and [1, 0, 1, 1] qualify: 7 in total.

Example 2

bits=[0, 0] → 0

There are no 1s at all, so no stretch qualifies.

Example 3

bits=[1, 0] → 1

Constraints

1 ≤ len(bits) ≤ 10⁵
bits[i] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Segment Tree Array Binary Search Divide and Conquer Ordered Set Merge Sort

Similar problems

Rank of an Arrangement Medium Smaller Values to the Right Hard Window Sums Within a Band Hard Pairs With a Steep Drop Hard Cost of Filling a Sorted Shelf Hard

Input

bits=[1, 0, 1, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.