# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/string/hard/copy-of-copy-of-copy-of-template.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.