> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/string/hard/copy-of-copy-of-copy-of-template.md).

# Copy of Copy of Copy of Template

## Problem Statement

<br>

You are given a binary string `s`.

Return the number of&#x20;

substrings with **dominant** ones.

A string has **dominant** ones if the number of ones in the string is **greater than or equal to** the **square** of the number of zeros in the string.

&#x20;

**Example 1:**

**Input:** s = "00011"

**Output:** 5

**Explanation:**

The substrings with dominant ones are shown in the table below.

| i | j | s\[i..j] | Number of Zeros | Number of Ones |
| - | - | -------- | --------------- | -------------- |
| 3 | 3 | 1        | 0               | 1              |
| 4 | 4 | 1        | 0               | 1              |
| 2 | 3 | 01       | 1               | 1              |
| 3 | 4 | 11       | 0               | 2              |
| 2 | 4 | 011      | 1               | 2              |

**Example 2:**

**Input:** s = "101101"

**Output:** 16

**Explanation:**

The substrings with **non-dominant** ones are shown in the table below.

Since there are 21 substrings total and 5 of them have non-dominant ones, it follows that there are 16 substrings with dominant ones.

| i | j | s\[i..j] | Number of Zeros | Number of Ones |
| - | - | -------- | --------------- | -------------- |
| 1 | 1 | 0        | 1               | 0              |
| 4 | 4 | 0        | 1               | 0              |
| 1 | 4 | 0110     | 2               | 2              |
| 0 | 4 | 10110    | 2               | 3              |
| 1 | 5 | 01101    | 2               | 3              |

&#x20;

**Constraints:**

* `1 <= s.length <= 4 * 104`
* `s` consists only of characters `'0'` and `'1'`.

## Intuition

```
Approach

Try to do a prefix sum find of approach

Starting from i -> Count number of substrings possible from that point
Check the condition, If we can incorporate more,
Let say
11110
Here we can take one more zero, So shift j pointer ahead, 
To add that substring to answer

Similarly others

```

### Links

<https://leetcode.com/problems/count-the-number-of-substrings-with-dominant-ones/>

### Video Links

<https://www.youtube.com/watch?v=hcGvofpRBg0&t=1030s&ab_channel=AbhinavAwasthi>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        int ans = 0;
        vector<int> pref(n,0);
        for(int i=0; i<s.size(); i++){
            if(s[i] == '1'){
                pref[i] = 1;
            }
        }
        for(int i=1; i<s.size(); i++){
            pref[i] = pref[i] + pref[i-1];
        }
     
        for(int i=0; i<s.size(); i++){
            
            for(int j=i; j<s.size(); j++){
                int ones = pref[j];
                if(i!=0) ones -= pref[i-1];
                int zeros = (j-i+1) - ones;

                if(zeros*zeros > ones){
                    j += (zeros*zeros - ones -1);
                }
                if(zeros*zeros <= ones){
                    ans ++;

                    if(zeros*zeros < ones){
                        int diff = sqrt(ones) - zeros;

                        if(j+diff >= n)
                            ans += (n-j-1);
                        else{
                            ans += diff;
                        }

                        j = j+diff;
                    }
                }
            }
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###