# Maximum count of 0s between two 1s in given range for Q queries

Given a binary string **S** of size **N**, and a 2D array** Q[][]** of queries consisting of **M** pairs of the form** {L, R}**, the task for each query is to find the maximum number of **0s** lying between two **1s** in the range** [L, R]**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:S = “1001010”, Q[][] = {{0, 4}, {0, 5}}Output:2 3Explanation:

The Queries are performed as per the following:

Query(0, 4):Print 2 as there are maximum 2 0’s lying between the indices 0 and 3 in the substring over the range [0, 4] i.e., “10010”.Query(0, 5):Print 3 as there are maximum 3 0’s lying between the indices 0 and 5 in the substring over the range [0, 5] i.e “100101”.

Input:S = “111”, Q[][] = {{0, 2}}Output:0

**Naive Approach:** The simplest approach to solve the given problem is to traverse the given array of queries **Q[][]** and for each query print the maximum number of **0s** between any two pair of **1s** by iterating over the range** [L, R]**.

**Time Complexity:** O(N*M)**Auxiliary Space:** O(1)

**Efficient Approach:** The above approach can be optimized using the concept of Prefix Sum Array which will result in the constant time calculation of a query. Follow the steps below to solve the problem:

- Initialize two arrays say
**leftBound[]**and**rightBound[]**to**0s**that are right to the most recent**1s**and the count of**0s**that are left to the most recent**1s**respectively. - Initialize two variables, say
**count**and**total**to update the arrays**leftBound[]**and**rightBound[]**. - Traverse the given string
**S**and if the current character is ‘**1**‘ then assign the value of**curr**to the variable**total**. Otherwise, increment**totals**by**1**and then assign the value of**curr**to the**rightBound[i]**. - Update the value of
**curr**and**totals**to**0**. - Traverse the string in the reverse order and in each iteration if the current character is ‘
**1**‘ then update the value of**curr**to the**total**. Otherwise, increment the value of**total**by**1**and then update the value of**curr**to**the lefttBound[i]**. - After completing the above steps, traverse the given array of queries
**Q[][]**and for each query print the value of**(leftBound[Q[i][0]] + rightBound[Q[i][1]] – total)**as the resultant maximum number of**0s**.

Below is the implementation of the above approach:

## C++

`#include <iostream>` `using` `namespace` `std;` `// Function to count the number of` `// 0s lying between the two 1s for` `// each query` `void` `countOsBetween1s(string S, ` `int` `N, ` `int` `Q[][2])` `{` ` ` `// Stores count of 0's that are` ` ` `// right to the most recent 1's` ` ` `int` `leftBound[N];` ` ` `// Stores count of 0's that are` ` ` `// left to the most recent 1's` ` ` `int` `rightBound[N];` ` ` `// Stores the count of zeros` ` ` `// in a prefix/suffix of array` ` ` `int` `count = 0;` ` ` `// Stores the count of total 0s` ` ` `int` `total = 0;` ` ` `// Traverse the string S` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// If current character is` ` ` `// '1'` ` ` `if` `(S[i] == ` `'1'` `) {` ` ` `count = total;` ` ` `}` ` ` `// Otherwise` ` ` `else` `if` `(S[i] == ` `'0'` `) {` ` ` `total++;` ` ` `}` ` ` `// Update the rightBound[i]` ` ` `rightBound[i] = count;` ` ` `}` ` ` `// Update count and total to 0` ` ` `count = 0;` ` ` `total = 0;` ` ` `// Traverse the string S in` ` ` `// reverse manner` ` ` `for` `(` `int` `i = N - 1; i >= 0; i--) {` ` ` `// If current character is` ` ` `// '1'` ` ` `if` `(S[i] == ` `'1'` `) {` ` ` `count = total;` ` ` `}` ` ` `// Otherwise` ` ` `else` `if` `(S[i] == ` `'0'` `) {` ` ` `total++;` ` ` `}` ` ` `// Update the leftBound[i]` ` ` `leftBound[i] = count;` ` ` `}` ` ` `// Traverse given query array` ` ` `for` `(` `int` `q = 0; q < 2; q++) {` ` ` `int` `L = Q[q][0];` ` ` `int` `R = Q[q][1];` ` ` `// Update the value of count` ` ` `count = leftBound[L] + rightBound[R] - total;` ` ` `// Print the count as the` ` ` `// result to the current` ` ` `// query [L, R]` ` ` `cout << count << ` `" "` `;` ` ` `}` `}` `// Driver Code` `int` `main()` `{` ` ` `string S = ` `"1001010"` `;` ` ` `int` `Q[][2] = { { 0, 4 }, { 0, 5 } };` ` ` `int` `N = S.length();` ` ` `countOsBetween1s(S, N, Q);` ` ` `return` `0;` `}` `// This code is contributed by Potta Lokesh` |

## Java

`// Java program for the above approach` `import` `java.lang.*;` `import` `java.util.*;` `class` `GFG {` ` ` `// Function to count the number of` ` ` `// 0s lying between the two 1s for` ` ` `// each query` ` ` `static` `void` `countOsBetween1s(` ` ` `String S, ` `int` `N, ` `int` `[][] Q)` ` ` `{` ` ` `// Stores count of 0's that are` ` ` `// right to the most recent 1's` ` ` `int` `[] leftBound = ` `new` `int` `[N];` ` ` `// Stores count of 0's that are` ` ` `// left to the most recent 1's` ` ` `int` `[] rightBound = ` `new` `int` `[N];` ` ` `// Stores the count of zeros` ` ` `// in a prefix/suffix of array` ` ` `int` `count = ` `0` `;` ` ` `// Stores the count of total 0s` ` ` `int` `total = ` `0` `;` ` ` `// Traverse the string S` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `// If current character is` ` ` `// '1'` ` ` `if` `(S.charAt(i) == ` `'1'` `) {` ` ` `count = total;` ` ` `}` ` ` `// Otherwise` ` ` `else` `if` `(S.charAt(i) == ` `'0'` `) {` ` ` `total++;` ` ` `}` ` ` `// Update the rightBound[i]` ` ` `rightBound[i] = count;` ` ` `}` ` ` `// Update count and total to 0` ` ` `count = ` `0` `;` ` ` `total = ` `0` `;` ` ` `// Traverse the string S in` ` ` `// reverse manner` ` ` `for` `(` `int` `i = N - ` `1` `; i >= ` `0` `; i--) {` ` ` `// If current character is` ` ` `// '1'` ` ` `if` `(S.charAt(i) == ` `'1'` `) {` ` ` `count = total;` ` ` `}` ` ` `// Otherwise` ` ` `else` `if` `(S.charAt(i) == ` `'0'` `) {` ` ` `total++;` ` ` `}` ` ` `// Update the leftBound[i]` ` ` `leftBound[i] = count;` ` ` `}` ` ` `// Traverse given query array` ` ` `for` `(` `int` `q = ` `0` `; q < Q.length; q++) {` ` ` `int` `L = Q[q][` `0` `];` ` ` `int` `R = Q[q][` `1` `];` ` ` `// Update the value of count` ` ` `count = leftBound[L] + rightBound[R] - total;` ` ` `// Print the count as the` ` ` `// result to the current` ` ` `// query [L, R]` ` ` `System.out.print(count + ` `" "` `);` ` ` `}` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `String S = ` `"1001010"` `;` ` ` `int` `Q[][] = { { ` `0` `, ` `4` `}, { ` `0` `, ` `5` `} };` ` ` `int` `N = S.length();` ` ` `countOsBetween1s(S, N, Q);` ` ` `}` `}` |

## Python3

`# Function to count the number of` `# 0s lying between the two 1s for` `# each query` `def` `countOsBetween1s(S, N, Q):` ` ` `# Stores count of 0's that are` ` ` `# right to the most recent 1's` ` ` `leftBound ` `=` `[` `0` `]` `*` `N` ` ` `# Stores count of 0's that are` ` ` `# left to the most recent 1's` ` ` `rightBound ` `=` `[` `0` `]` `*` `N` ` ` `# Stores the count of zeros` ` ` `# in a prefix/suffix of array` ` ` `count ` `=` `0` ` ` `# Stores the count of total 0s` ` ` `total ` `=` `0` ` ` `# Traverse the string S` ` ` `for` `i ` `in` `range` `(N):` ` ` `# If current character is` ` ` `# '1'` ` ` `if` `(S[i] ` `=` `=` `'1'` `):` ` ` `count ` `=` `total` ` ` `# Otherwise` ` ` `elif` `(S[i] ` `=` `=` `'0'` `):` ` ` `total ` `+` `=` `1` ` ` `# Update the rightBound[i]` ` ` `rightBound[i] ` `=` `count` ` ` `# Update count and total to 0` ` ` `count ` `=` `0` ` ` `total ` `=` `0` ` ` `# Traverse the string S in` ` ` `# reverse manner` ` ` `for` `i ` `in` `range` `(N ` `-` `1` `, ` `-` `1` `, ` `-` `1` `):` ` ` `# If current character is` ` ` `# '1'` ` ` `if` `(S[i] ` `=` `=` `'1'` `):` ` ` `count ` `=` `total` ` ` `# Otherwise` ` ` `elif` `(S[i] ` `=` `=` `'0'` `):` ` ` `total ` `+` `=` `1` ` ` `# Update the leftBound[i]` ` ` `leftBound[i] ` `=` `count` ` ` `# Traverse given query array` ` ` `for` `q ` `in` `range` `(` `2` `):` ` ` `L ` `=` `Q[q][` `0` `]` ` ` `R ` `=` `Q[q][` `1` `]` ` ` `# Update the value of count` ` ` `count ` `=` `leftBound[L] ` `+` `rightBound[R] ` `-` `total` ` ` `# Print the count as the` ` ` `# result to the current` ` ` `# query [L, R]` ` ` `print` `(count, end` `=` `" "` `)` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `S ` `=` `"1001010"` ` ` `Q ` `=` `[[` `0` `, ` `4` `], [` `0` `, ` `5` `]]` ` ` `N ` `=` `len` `(S)` ` ` `countOsBetween1s(S, N, Q)` ` ` `# This code is contributed by ukasp.` |

## C#

`// C# program for the above approach` `using` `System;` `public` `class` `GFG {` ` ` `// Function to count the number of` ` ` `// 0s lying between the two 1s for` ` ` `// each query` ` ` `static` `void` `countOsBetween1s(` ` ` `String S, ` `int` `N, ` `int` `[,] Q)` ` ` `{` ` ` `// Stores count of 0's that are` ` ` `// right to the most recent 1's` ` ` `int` `[] leftBound = ` `new` `int` `[N];` ` ` `// Stores count of 0's that are` ` ` `// left to the most recent 1's` ` ` `int` `[] rightBound = ` `new` `int` `[N];` ` ` `// Stores the count of zeros` ` ` `// in a prefix/suffix of array` ` ` `int` `count = 0;` ` ` `// Stores the count of total 0s` ` ` `int` `total = 0;` ` ` `// Traverse the string S` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// If current character is` ` ` `// '1'` ` ` `if` `(S[i] == ` `'1'` `) {` ` ` `count = total;` ` ` `}` ` ` `// Otherwise` ` ` `else` `if` `(S[i] == ` `'0'` `) {` ` ` `total++;` ` ` `}` ` ` `// Update the rightBound[i]` ` ` `rightBound[i] = count;` ` ` `}` ` ` `// Update count and total to 0` ` ` `count = 0;` ` ` `total = 0;` ` ` `// Traverse the string S in` ` ` `// reverse manner` ` ` `for` `(` `int` `i = N - 1; i >= 0; i--) {` ` ` `// If current character is` ` ` `// '1'` ` ` `if` `(S[i] == ` `'1'` `) {` ` ` `count = total;` ` ` `}` ` ` `// Otherwise` ` ` `else` `if` `(S[i] == ` `'0'` `) {` ` ` `total++;` ` ` `}` ` ` `// Update the leftBound[i]` ` ` `leftBound[i] = count;` ` ` `}` ` ` `// Traverse given query array` ` ` `for` `(` `int` `q = 0; q < Q.GetLength(0); q++) {` ` ` `int` `L = Q[q,0];` ` ` `int` `R = Q[q,1];` ` ` `// Update the value of count` ` ` `count = leftBound[L] + rightBound[R] - total;` ` ` `// Print the count as the` ` ` `// result to the current` ` ` `// query [L, R]` ` ` `Console.Write(count + ` `" "` `);` ` ` `}` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `String S = ` `"1001010"` `;` ` ` `int` `[,]Q = { { 0, 4 }, { 0, 5 } };` ` ` `int` `N = S.Length;` ` ` `countOsBetween1s(S, N, Q);` ` ` `}` `}` `// This code is contributed by Amit Katiyar` |

## Javascript

`<script>` `// Function to count the number of` `// 0s lying between the two 1s for` `// each query` `function` `countOsBetween1s(S, N, Q) {` ` ` `// Stores count of 0's that are` ` ` `// right to the most recent 1's` ` ` `let leftBound = ` `new` `Array(N);` ` ` `// Stores count of 0's that are` ` ` `// left to the most recent 1's` ` ` `let rightBound = ` `new` `Array(N);` ` ` `// Stores the count of zeros` ` ` `// in a prefix/suffix of array` ` ` `let count = 0;` ` ` `// Stores the count of total 0s` ` ` `let total = 0;` ` ` `// Traverse the string S` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `// If current character is` ` ` `// '1'` ` ` `if` `(S[i] == ` `'1'` `) {` ` ` `count = total;` ` ` `}` ` ` `// Otherwise` ` ` `else` `if` `(S[i] == ` `'0'` `) {` ` ` `total++;` ` ` `}` ` ` `// Update the rightBound[i]` ` ` `rightBound[i] = count;` ` ` `}` ` ` `// Update count and total to 0` ` ` `count = 0;` ` ` `total = 0;` ` ` `// Traverse the string S in` ` ` `// reverse manner` ` ` `for` `(let i = N - 1; i >= 0; i--) {` ` ` `// If current character is` ` ` `// '1'` ` ` `if` `(S[i] == ` `'1'` `) {` ` ` `count = total;` ` ` `}` ` ` `// Otherwise` ` ` `else` `if` `(S[i] == ` `'0'` `) {` ` ` `total++;` ` ` `}` ` ` `// Update the leftBound[i]` ` ` `leftBound[i] = count;` ` ` `}` ` ` `// Traverse given query array` ` ` `for` `(let q = 0; q < 2; q++) {` ` ` `let L = Q[q][0];` ` ` `let R = Q[q][1];` ` ` `// Update the value of count` ` ` `count = leftBound[L] + rightBound[R] - total;` ` ` `// Print the count as the` ` ` `// result to the current` ` ` `// query [L, R]` ` ` `document.write(count + ` `" "` `);` ` ` `}` `}` `// Driver Code` `let S = ` `"1001010"` `;` `let Q = [[0, 4], [0, 5]];` `let N = S.length;` `countOsBetween1s(S, N, Q);` `// This code is contributed by gfgking` `</script>` |

**Output:**

2 3

**Time Complexity:** O(N + M)**Auxiliary Space:** O(N)