Ones Beat Zeros Squared

Medium

You are given a string bits made of the characters 0 and 1. Call a substring *heavy* if the number of ones in it is at least the **square** of the number of zeros in it. For example, 0111 is heavy (3 ≥ 1²), while 00111 is not (3 < 2²). Return the number of non-empty heavy substrings of bits. Substrings at different positions count separately, even if their contents match.

Example 1

bits="1101" → 9

Of the 10 substrings only the lone 0 fails (one zero, no ones). For instance, 101 is fine: 2 ones ≥ 1².

Example 2

bits="0000" → 0

Every substring has a zero and no ones, so the answer is 0.

Example 3

bits="1001111" → 19

Constraints

1 ≤ len(bits) ≤ 4 · 10⁴
bits consists only of 0 and 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Enumeration Sliding Window

Similar problems

Odd Versus Even in a Window Hard Longest Repeat-Free Stretch Medium Two-Letter Stretch Medium Recurring Gene Windows Medium Window with Few Kinds of Letters Medium

Input

bits="1101"

Expected

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