Número de substrings con una longitud divisible por el número de 1 que contiene

Posted on by Rudeus Greyrat

Dada una string binaria S que consta de solo 0 y 1. Cuente el número de substrings de esta string de modo que la longitud de la substring sea divisible por el número de 1 en la substring.

Ejemplos:

Entrada: S = “01010” 
Salida: 10

Entrada: S = “1111100000” 
Salida: 25 

Enfoque ingenuo: 

  • Repita todas las substrings y para cada substring cuente el número de 1. Si la longitud de la substring es divisible por el conteo de 1, aumente el conteo. Este enfoque tomará tiempo O(N 3 ).
  • Para hacer que la solución sea más eficiente, en lugar de recorrer toda la substring para contar el número de 1 que contiene, podemos usar Prefix Sum Array .

número de 1 en la substring [l: r] = prefix_sum[r] – prefix_sum[l – 1]  

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ program to count number of
// substring under given condition
#include <bits/stdc++.h>
using namespace std;
 
// Function return count of
// such substring
int countOfSubstrings(string s)
{
    int n = s.length();
 
    int prefix_sum[n] = { 0 };
 
    // Mark 1 at those indices
    // where '1' appears
    for (int i = 0; i < n; i++) {
        if (s[i] == '1')
            prefix_sum[i] = 1;
    }
 
    // Take prefix sum
    for (int i = 1; i < n; i++)
        prefix_sum[i] += prefix_sum[i - 1];
 
    int answer = 0;
 
    // Iterate through all the
    // substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int countOfOnes = prefix_sum[j]
                - (i - 1 >= 0 ?
                   prefix_sum[i - 1] : 0);
            int length = j - i + 1;
 
            if (countOfOnes > 0 &&
                length % countOfOnes == 0)
                answer++;
        }
    }
    return answer;
}
 
// Driver Code
int main()
{
    string S = "1111100000";
 
    cout << countOfSubstrings(S);
 
    return 0;
}

Java

// Java program to count number of
// subString under given condition
 
import java.util.*;
 
class GFG{
 
// Function return count of
// such substring
static int countOfSubStrings(String s)
{
    int n = s.length();
 
    int []prefix_sum = new int[n];
 
    // Mark 1 at those indices
    // where '1' appears
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '1')
            prefix_sum[i] = 1;
    }
     
    // Take prefix sum
    for (int i = 1; i < n; i++)
        prefix_sum[i] += prefix_sum[i - 1];
 
    int answer = 0;
     
    // Iterate through all the
    // subStrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int countOfOnes = prefix_sum[j]
                - (i - 1 >= 0 ?
                prefix_sum[i - 1] : 0);
            int length = j - i + 1;
 
            if (countOfOnes > 0 &&
                length % countOfOnes == 0)
                answer++;
        }
    }
    return answer;
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "1111100000";
 
    System.out.print(countOfSubStrings(S));
 
}
}
 
// This code contributed by sapnasingh4991

Python3

# Python3 program to count number of
# substring under given condition
 
# Function return count of
# such substring
def countOfSubstrings(s):
    n = len(s)
    prefix_sum = [0 for i in range(n)]
 
    # Mark 1 at those indices
    # where '1' appears
    for i in range(n):
        if (s[i] == '1'):
            prefix_sum[i] = 1
 
    # Take prefix sum
    for i in range(1, n, 1):
        prefix_sum[i] += prefix_sum[i - 1]
 
    answer = 0
 
    # Iterate through all the
    # substrings
    for i in range(n):
        for j in range(i, n, 1):
            if (i - 1 >= 0):
                countOfOnes = prefix_sum[j]- prefix_sum[i - 1]
            else:
                countOfOnes = prefix_sum[j]
            length = j - i + 1
 
            if (countOfOnes > 0 and length % countOfOnes == 0):
                answer += 1
 
    return answer
 
# Driver Code
if __name__ == '__main__':
    S = "1111100000"
 
    print(countOfSubstrings(S))
 
# This code is contributed by Bhupendra_Singh

C#

// C# program to count number of
// subString under given condition
using System;
 
class GFG{
 
// Function return count of
// such substring
static int countOfSubStrings(String s)
{
    int n = s.Length;
    int []prefix_sum = new int[n];
 
    // Mark 1 at those indices
    // where '1' appears
    for(int i = 0; i < n; i++)
    {
        if (s[i] == '1')
            prefix_sum[i] = 1;
    }
     
    // Take prefix sum
    for(int i = 1; i < n; i++)
        prefix_sum[i] += prefix_sum[i - 1];
 
    int answer = 0;
     
    // Iterate through all the
    // subStrings
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            int countOfOnes = prefix_sum[j] -
                                  (i - 1 >= 0 ?
                              prefix_sum[i - 1] : 0);
            int length = j - i + 1;
     
            if (countOfOnes > 0 &&
                length % countOfOnes == 0)
            answer++;
        }
    }
    return answer;
}
 
// Driver Code
public static void Main(String[] args)
{
    String S = "1111100000";
    Console.Write(countOfSubStrings(S));
}
}
 
// This code is contributed by Rohit_ranjan

Javascript

<script>
 
// Javascript program to count number of
// subString under given condition
 
// Function return count of
// such substring
function countOfSubStrings(s)
{
    let n = s.length;
   
    let prefix_sum = Array.from({length: n}, (_, i) => 0);
   
    // Mark 1 at those indices
    // where '1' appears
    for (let i = 0; i < n; i++) {
        if (s[i] == '1')
            prefix_sum[i] = 1;
    }
       
    // Take prefix sum
    for (let i = 1; i < n; i++)
        prefix_sum[i] += prefix_sum[i - 1];
   
    let answer = 0;
       
    // Iterate through all the
    // subStrings
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            let countOfOnes = prefix_sum[j]
                - (i - 1 >= 0 ?
                prefix_sum[i - 1] : 0);
            let length = j - i + 1;
   
            if (countOfOnes > 0 &&
                length % countOfOnes == 0)
                answer++;
        }
    }
    return answer;
}
 
// Driver Code
     
    let S = "1111100000";
   
    document.write(countOfSubStrings(S));
                     
</script>
Producción: 

25

 

Complejidad del tiempo: O(N 2 )

Espacio Auxiliar: O(N)

Enfoque eficiente: 

  • Usemos la array de suma de prefijos como se discutió en el enfoque anterior. Tomemos una substring [l:r] que sigue la condición dada, podemos decir que:

 r – l + 1 = k * (prefix_sum[r] – prefix_sum[l-1]), donde k es un número entero 

  • Esto también se puede escribir como:

r – k * suma_prefijo[r] = l – 1 – k * suma_prefijo[l-1] 

Observando esta ecuación, podemos crear otra array de B[i] = i – k * prefix_sum[i], para 0 <= k < n. Entonces, el problema ahora es calcular el número de pares de enteros iguales en B para cada k. 

  • Tomemos un número fijo x. Si k > x, entonces como r – l + 1 <= n (para cualquier par de l, r), obtenemos la siguiente desigualdad:

 suma_prefijo[r] – suma_prefijo[l-1] = (r – l + 1)/k <= n/x  

  • Esto continúa para mostrar que el número de unos y k no es grande en las substrings que satisfacen las condiciones dadas. (esto es solo para la estimación de la eficiencia). Ahora, para k <= x, necesitamos calcular el número de pares de enteros iguales. Aquí se cumple la siguiente desigualdad:

(-1) *n*x <= i – k – suma_prefijo[i] <= n 

  • Entonces, podemos poner todos los números en una array para cada k de forma independiente y encontrar el número de enteros iguales.
  • El siguiente paso sería fijar los valores de l e iterar sobre el número de 1 en la string, y para cada valor obtener los límites de r. Para una cuenta dada del número de 1, podemos evaluar qué resto dará r. El problema ahora es calcular el número de números enteros en algunos segmentos, lo que da un resto fijo (rem) cuando se divide por algún número entero fijo. Este cálculo se puede hacer en O(1). Además, tenga en cuenta que es importante contar solo los valores de r para los que k > x. 
     

A continuación se muestra la implementación del enfoque anterior. 

C++

// C++ program to count number of
// substring under given condition
#include <bits/stdc++.h>
using namespace std;
 
// Function return count of such
// substring
int countOfSubstrings(string s)
{
 
    int n = s.length();
 
    // Selection of adequate x value
    int x = sqrt(n);
 
    // Store where 1's are located
    vector<int> ones;
 
    for (int i = 0; i < n; i++) {
        if (s[i] == '1')
            ones.push_back(i);
    }
 
    // If there are no ones,
    // then answer is 0
    if (ones.size() == 0)
        return 0;
 
    // For ease of implementation
    ones.push_back(n);
 
    // Count storage
    vector<int> totCount(n * x + n);
 
    int sum = 0;
 
    // Iterate on all k values less
    // than fixed x
    for (int k = 0; k <= x; k++) {
        // Keeps a count of 1's occured
        // during string traversal
        int now = 0;
        totCount[k * n]++;
 
        // Iterate on string and modify
        // the totCount
        for (int j = 1; j <= n; j++) {
            // If this character is 1
            if (s[j - 1] == '1')
                now++;
            int index = j - k * now;
 
            // Add to the final sum/count
            sum += totCount[index + k * n];
             
            // Increase totCount at exterior
            // position
            totCount[index + k * n]++;
        }
        now = 0;
        totCount[k * n]--;
 
        for (int j = 1; j <= n; j++) {
            if (s[j - 1] == '1')
                now++;
            int index = j - k * now;
 
            // Reduce totCount at index + k*n
            totCount[index + k * n]--;
        }
    }
 
    // Slightly modified prefix sum storage
    int prefix_sum[n];
    memset(prefix_sum, -1, sizeof(prefix_sum));
 
    // Number of 1's till i-1
    int cnt = 0;
 
    for (int i = 0; i < n; i++) {
        prefix_sum[i] = cnt;
        if (s[i] == '1')
            cnt++;
    }
 
    // Traversing over string considering
    // each position and finding bounds
    // and count using the inequalities
    for (int k = 0; k < n; k++)
    {
        for (int j = 1; j <= (n / x)
             && prefix_sum[k] + j <= cnt; j++)
        {
            // Calculating bounds for l and r
            int l = ones[prefix_sum[k] + j - 1]
                    - k + 1;
             
            int r = ones[prefix_sum[k] + j] - k;
             
            l = max(l, j * (x + 1));
 
            // If valid then add to answer
            if (l <= r) {
                sum += r / j - (l - 1) / j;
            }
        }
    }
 
    return sum;
}
int main()
{
    string S = "1111100000";
 
    cout << countOfSubstrings(S);
 
    return 0;
}

Java

// Java program to count number of
// subString under given condition
import java.util.*;
 
class GFG{
 
// Function return count of such
// substring
static int countOfSubStrings(String s)
{
    int n = s.length();
 
    // Selection of adequate x value
    int x = (int)Math.sqrt(n);
 
    // Store where 1's are located
    Vector<Integer> ones = new Vector<Integer>();
 
    for(int i = 0; i < n; i++)
    {
        if (s.charAt(i) == '1')
            ones.add(i);
    }
 
    // If there are no ones,
    // then answer is 0
    if (ones.size() == 0)
        return 0;
 
    // For ease of implementation
    ones.add(n);
 
    // Count storage
    int []totCount = new int[n * x + n];
 
    int sum = 0;
 
    // Iterate on all k values less
    // than fixed x
    for(int k = 0; k <= x; k++)
    {
         
        // Keeps a count of 1's occured
        // during String traversal
        int now = 0;
        totCount[k * n]++;
 
        // Iterate on String and modify
        // the totCount
        for(int j = 1; j <= n; j++)
        {
             
            // If this character is 1
            if (s.charAt(j - 1) == '1')
                now++;
                 
            int index = j - k * now;
 
            // Add to the final sum/count
            sum += totCount[index + k * n];
             
            // Increase totCount at exterior
            // position
            totCount[index + k * n]++;
        }
        now = 0;
        totCount[k * n]--;
 
        for(int j = 1; j <= n; j++)
        {
            if (s.charAt(j - 1) == '1')
                now++;
                 
            int index = j - k * now;
 
            // Reduce totCount at index + k*n
            totCount[index + k * n]--;
        }
    }
 
    // Slightly modified prefix sum storage
    int []prefix_sum = new int[n];
    Arrays.fill(prefix_sum, -1);
 
    // Number of 1's till i-1
    int cnt = 0;
 
    for(int i = 0; i < n; i++)
    {
        prefix_sum[i] = cnt;
        if (s.charAt(i) == '1')
            cnt++;
    }
 
    // Traversing over String considering
    // each position and finding bounds
    // and count using the inequalities
    for(int k = 0; k < n; k++)
    {
        for(int j = 1; j <= (n / x) &&
            prefix_sum[k] + j <= cnt; j++)
        {
             
            // Calculating bounds for l and r
            int l = ones.get(prefix_sum[k] + j - 1)-
                                             k + 1;
             
            int r = ones.get(prefix_sum[k] + j) - k;
            l = Math.max(l, j * (x + 1));
 
            // If valid then add to answer
            if (l <= r)
            {
                sum += r / j - (l - 1) / j;
            }
        }
    }
    return sum;
}
 
// Driver code
public static void main(String[] args)
{
    String S = "1111100000";
 
    System.out.print(countOfSubStrings(S));
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to count number of
# substring under given condition
import math
 
# Function return count of such
# substring
def countOfSubstrings(s):
 
    n = len(s)
 
    # Selection of adequate x value
    x = int(math.sqrt(n))
 
    # Store where 1's are located
    ones = []
 
    for i in range (n):
        if (s[i] == '1'):
            ones.append(i)
 
    # If there are no ones,
    # then answer is 0
    if (len(ones) == 0):
        return 0
 
    # For ease of implementation
    ones.append(n)
 
    # Count storage
    totCount = [0] * (n * x + n)
 
    sum = 0
 
    # Iterate on all k values less
    # than fixed x
    for k in range(x + 1):
         
        # Keeps a count of 1's occured
        # during string traversal
        now = 0
        totCount[k * n] += 1
 
        # Iterate on string and modify
        # the totCount
        for j in range(1, n + 1):
             
            # If this character is 1
            if (s[j - 1] == '1'):
                now += 1
            index = j - k * now
 
            # Add to the final sum/count
            sum += totCount[index + k * n]
             
            # Increase totCount at exterior
            # position
            totCount[index + k * n] += 1
         
        now = 0
        totCount[k * n] -= 1
 
        for j in range(1, n + 1):
            if (s[j - 1] == '1'):
                now += 1
            index = j - k * now
 
            # Reduce totCount at index + k*n
            totCount[index + k * n] -= 1
 
    # Slightly modified prefix sum storage
    prefix_sum = [-1] * n
 
    # Number of 1's till i-1
    cnt = 0
 
    for i in range(n):
        prefix_sum[i] = cnt
        if (s[i] == '1'):
            cnt += 1
     
    # Traversing over string considering
    # each position and finding bounds
    # and count using the inequalities
    for k in range(n):
        j = 1
        while (j <= (n // x) and
               prefix_sum[k] + j <= cnt):
         
            # Calculating bounds for l and r
            l = (ones[prefix_sum[k] + j - 1] -
                                      k + 1)
             
            r = ones[prefix_sum[k] + j] - k
            l = max(l, j * (x + 1))
 
            # If valid then add to answer
            if (l <= r):
                sum += r // j - (l - 1) // j
             
            j += 1
 
    return sum
 
# Driver code
if __name__ == "__main__":
     
    S = "1111100000"
 
    print (countOfSubstrings(S))
 
# This code is contributed by chitranayal

C#

// C# program to count number of
// subString under given condition
using System;
using System.Collections.Generic;
  
class GFG{
  
// Function return count of such
// substring
static int countOfSubStrings(String s)
{
    int n = s.Length;
  
    // Selection of adequate x value
    int x = (int)Math.Sqrt(n);
  
    // Store where 1's are located
    List<int> ones = new List<int>();
  
    for(int i = 0; i < n; i++)
    {
        if (s[i] == '1')
            ones.Add(i);
    }
  
    // If there are no ones,
    // then answer is 0
    if (ones.Count == 0)
        return 0;
  
    // For ease of implementation
    ones.Add(n);
  
    // Count storage
    int []totCount = new int[n * x + n];
  
    int sum = 0;
  
    // Iterate on all k values less
    // than fixed x
    for(int k = 0; k <= x; k++)
    {
          
        // Keeps a count of 1's occured
        // during String traversal
        int now = 0;
        totCount[k * n]++;
  
        // Iterate on String and modify
        // the totCount
        for(int j = 1; j <= n; j++)
        {
              
            // If this character is 1
            if (s[j-1] == '1')
                now++;
                  
            int index = j - k * now;
  
            // Add to the readonly sum/count
            sum += totCount[index + k * n];
              
            // Increase totCount at exterior
            // position
            totCount[index + k * n]++;
        }
        now = 0;
        totCount[k * n]--;
  
        for(int j = 1; j <= n; j++)
        {
            if (s[j-1] == '1')
                now++;
                  
            int index = j - k * now;
  
            // Reduce totCount at index + k*n
            totCount[index + k * n]--;
        }
    }
  
    // Slightly modified prefix sum storage
    int []prefix_sum = new int[n];
    for(int i = 0; i < n; i++)
        prefix_sum [i]= -1;
  
    // Number of 1's till i-1
    int cnt = 0;
  
    for(int i = 0; i < n; i++)
    {
        prefix_sum[i] = cnt;
        if (s[i] == '1')
            cnt++;
    }
  
    // Traversing over String considering
    // each position and finding bounds
    // and count using the inequalities
    for(int k = 0; k < n; k++)
    {
        for(int j = 1; j <= (n / x) &&
            prefix_sum[k] + j <= cnt; j++)
        {
              
            // Calculating bounds for l and r
            int l = ones[prefix_sum[k] + j - 1]-
                                         k + 1;
              
            int r = ones[prefix_sum[k] + j] - k;
            l = Math.Max(l, j * (x + 1));
  
            // If valid then add to answer
            if (l <= r)
            {
                sum += r / j - (l - 1) / j;
            }
        }
    }
    return sum;
}
  
// Driver code
public static void Main(String[] args)
{
    String S = "1111100000";
  
    Console.Write(countOfSubStrings(S));
}
}
  
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript program to count number of
// substring under given condition
 
// Function return count of such
// substring
function countOfSubstrings(s)
{
 
    var n = s.length;
 
    // Selection of adequate x value
    var x = parseInt(Math.sqrt(n));
 
    // Store where 1's are located
    var ones = [];
 
    for (var i = 0; i < n; i++) {
        if (s[i] == '1')
            ones.push(i);
    }
 
    // If there are no ones,
    // then answer is 0
    if (ones.length == 0)
        return 0;
 
    // For ease of implementation
    ones.push(n);
 
    // Count storage
    var totCount = Array(n * x + n).fill(0);
 
    var sum = 0;
 
    // Iterate on all k values less
    // than fixed x
    for (var k = 0; k <= x; k++) {
        // Keeps a count of 1's occured
        // during string traversal
        var now = 0;
        totCount[k * n]++;
 
        // Iterate on string and modify
        // the totCount
        for (var j = 1; j <= n; j++) {
            // If this character is 1
            if (s[j - 1] == '1')
                now++;
            var index = j - k * now;
 
            // Add to the final sum/count
            sum += totCount[index + k * n];
             
            // Increase totCount at exterior
            // position
            totCount[index + k * n]++;
        }
        now = 0;
        totCount[k * n]--;
 
        for (var j = 1; j <= n; j++) {
            if (s[j - 1] == '1')
                now++;
            var index = j - k * now;
 
            // Reduce totCount at index + k*n
            totCount[index + k * n]--;
        }
    }
 
    // Slightly modified prefix sum storage
    var prefix_sum = Array(n).fill(-1);
 
    // Number of 1's till i-1
    var cnt = 0;
 
    for (var i = 0; i < n; i++) {
        prefix_sum[i] = cnt;
        if (s[i] == '1')
            cnt++;
    }
 
    // Traversing over string considering
    // each position and finding bounds
    // and count using the inequalities
    for (var k = 0; k < n; k++)
    {
        for (var j = 1; j <= parseInt(n / x)
             && prefix_sum[k] + j <= cnt; j++)
        {
            // Calculating bounds for l and r
            var l = ones[prefix_sum[k] + j - 1]
                    - k + 1;
             
            var r = ones[prefix_sum[k] + j] - k;
             
            l = Math.max(l, j * (x + 1));
 
            // If valid then add to answer
            if (l <= r) {
                sum += parseInt(r / j) - parseInt((l - 1) / j);
            }
        }
    }
 
    return sum;
}
 
 
var S = "1111100000";
document.write( countOfSubstrings(S));
 
 
</script>
Producción: 

25

Complejidad del tiempo: O(N\sqrt{N})  

Espacio Auxiliar: O(N 3/2 )

Publicación traducida automáticamente

Artículo escrito por king_tsar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *