Dada una string binaria S de tamaño N y una array 2D Q[][] de consultas que consta de M pares de la forma {L, R} , la tarea para cada consulta es encontrar el número máximo de 0 que se encuentran entre dos 1 en el rango [L, R] .
Ejemplos:
Entrada: S = “1001010”, Q[][] = {{0, 4}, {0, 5}}
Salida: 2 3
Explicación:
Las consultas se realizan de la siguiente manera:
- Consulta (0, 4): Imprima 2 ya que hay un máximo de 2 0 entre los índices 0 y 3 en la substring sobre el rango [0, 4], es decir, «10010».
- Consulta (0, 5): Imprima 3 ya que hay un máximo de 3 0 entre los índices 0 y 5 en la substring sobre el rango [0, 5], es decir, «100101».
Entrada: S = “111”, Q[][] = {{0, 2}}
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es atravesar la array dada de consultas Q[][] y para cada consulta imprimir el número máximo de 0 entre dos pares de 1 iterando sobre el rango [L, R] .
Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el concepto de array de suma de prefijos que dará como resultado el cálculo de tiempo constante de una consulta. Siga los pasos a continuación para resolver el problema:
- Inicialice dos arrays , digamos leftBound[] y rightBound[], para almacenar el conteo de 0 que están a la derecha de los 1 más recientes y el conteo de 0 que quedan con los 1 más recientes , respectivamente.
- Inicialice dos variables, digamos count y total para actualizar las arrays leftBound[] y rightBound[] .
- Recorra la string dada S y si el carácter actual es ‘ 1 ‘ entonces asigne el valor de curr a la variable total . De lo contrario, incremente los totales en 1 y luego asigne el valor de curr a rightBound[i] .
- Actualice el valor de curr y totales a 0 .
- Recorra la string en el orden inverso y en cada iteración si el carácter actual es ‘ 1 ‘ entonces actualice el valor de curr al total . De lo contrario, incremente el valor de total en 1 y luego actualice el valor de curr a lefttBound[i] .
- Después de completar los pasos anteriores, recorra la array dada de consultas Q[][] y para cada consulta imprima el valor de (LímiteIzquierdo[Q[i][0]] + LímiteDerecho[Q[i][1]] – total) como el número máximo resultante de 0s .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
2 3
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)