Recuento de substrings cuyo equivalente decimal es mayor o igual a K

Posted on by Rudeus Greyrat

Dado un entero K y una string binaria S de longitud N , la tarea es encontrar el número de substrings  cuyo equivalente decimal es mayor o igual que K.

Ejemplos:  

Entrada: K = 3, S = “11100” 
Salida: 8 
Explicación: 
Hay 8 substrings cuyo equivalente decimal es mayor o igual a 3, como se menciona a continuación: 
Substring – Equivalente decimal 
“100” – 4, 
“1100” – 12, 
«11100» – 28, 
«110» – 6, 
«1110» – 14, 
«11» – 3, 
«111» – 7, 
«11» – 3

Entrada: K = 5, S = “10110110” 
Salida: 19 
Explicación: 
Hay 19 substrings cuyo equivalente decimal es mayor o igual a 5. 

Enfoque ingenuo: descubra todas las substrings y, para cada substring, conviértalas de binario a decimal y verifique si es mayor o igual a K. Cuente el número de cada substring encontrada.

Enfoque eficiente: uso de la técnica de dos puntos  

  1. La idea es mantener dos punteros L y R .
  2. Fije la posición del puntero derecho ‘R’ de la substring a la longitud – 1 e itere con un ciclo hasta que el valor de R sea positivo: 
    • Inicialice el valor de L a R, para considerar la substring de longitud 1
    • Disminuya el valor de L en 1 hasta que el equivalente decimal de la substring de longitud R – L + 1 sea mayor o igual que K
    • Incremente el contador por el número de bits a la izquierda de la L.

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

C++

// C++ implementation to count the
// substrings whose decimal equivalent
// is greater than or equal to K
#include <bits/stdc++.h>
using namespace std;
 
// Function to count number of
// substring whose decimal equivalent
// is greater than or equal to K
unsigned long long countSubstr(
    string& s, int k)
{
 
    int n = s.length();
 
    // Left pointer of the substring
    int l = n - 1;
 
    // Right pointer of the substring
    int r = n - 1;
    int arr[n];
    int last_indexof1 = -1;
 
    // Loop to maintain the last
    // occurrence of the 1 in the string
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            arr[i] = i;
            last_indexof1 = i;
        }
        else {
            arr[i] = last_indexof1;
        }
    }
 
    // Variable to count the substring
    unsigned long long no_of_substr = 0;
 
    // Loop to maintain the every
    // possible end index of the substring
    for (r = n - 1; r >= 0; r--) {
        l = r;
 
        // Loop to find the substring
        // whose decimal equivalent is
        // greater than or equal to K
        while (l >= 0
               && (r - l + 1) <= 64
               && stoull(
                      s.substr(l, r - l + 1), 0, 2)
                      < k) {
            l--;
        }
 
        // Condition to check no
        // of bits is out of bound
        if (r - l + 1 <= 64)
            no_of_substr += l + 1;
        else {
            no_of_substr += arr[l + 1] + 1;
        }
    }
    return no_of_substr;
}
 
// Driver Code
int main()
{
    string s = "11100";
    unsigned long long int k = 3;
    cout << countSubstr(s, k);
}

Java

// Java implementation to count the
// subStrings whose decimal equivalent
// is greater than or equal to K
import java.util.*;
 
class GFG{
  
// Function to count number of
// subString whose decimal equivalent
// is greater than or equal to K
static long countSubstr(
    String s, int k)
{
  
    int n = s.length();
  
    // Left pointer of the subString
    int l = n - 1;
  
    // Right pointer of the subString
    int r = n - 1;
    int []arr = new int[n];
    int last_indexof1 = -1;
  
    // Loop to maintain the last
    // occurrence of the 1 in the String
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '1') {
            arr[i] = i;
            last_indexof1 = i;
        }
        else {
            arr[i] = last_indexof1;
        }
    }
  
    // Variable to count the subString
    long no_of_substr = 0;
  
    // Loop to maintain the every
    // possible end index of the subString
    for (r = n - 1; r >= 0; r--) {
        l = r;
  
        // Loop to find the subString
        // whose decimal equivalent is
        // greater than or equal to K
        while (l >= 0
               && (r - l + 1) <= 64
               && Integer.valueOf(s.substring(l, r + 1),2)
                      < k) {
            l--;
        }
  
        // Condition to check no
        // of bits is out of bound
        if (r - l + 1 <= 64)
            no_of_substr += l + 1;
        else {
            no_of_substr += arr[l + 1] + 1;
        }
    }
    return no_of_substr;
}
  
// Driver Code
public static void main(String[] args)
{
    String s = "11100";
    int k = 3;
    System.out.println(countSubstr(s, k));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation to count the
# substrings whose decimal equivalent
# is greater than or equal to K
 
# Function to count number of
# substring whose decimal equivalent
# is greater than or equal to K
def countSubstr(s, k):
 
    n = len(s)
 
    # Left pointer of the substring
    l = n - 1
 
    # Right pointer of the substring
    r = n - 1
    arr = [0]*n
    last_indexof1 = -1
 
    # Loop to maintain the last
    # occurrence of the 1 in the string
    for i in range(n):
        if (s[i] == '1'):
            arr[i] = i
            last_indexof1 = i
 
        else:
            arr[i] = last_indexof1
 
    # Variable to count the substring
    no_of_substr = 0
 
    # Loop to maintain the every
    # possible end index of the substring
    for r in range(n - 1, -1, -1):
        l = r
 
        # Loop to find the substring
        # whose decimal equivalent is
        # greater than or equal to K
        while (l >= 0 and (r - l + 1) <= 64 and int(s[l:r + 1], 2)< k):
            l -= 1
 
        # Condition to check no
        # of bits is out of bound
        if (r - l + 1 <= 64):
            no_of_substr += l + 1
        else:
            no_of_substr += arr[l + 1] + 1
 
    return no_of_substr
 
# Driver Code
 
s = "11100"
k = 3
print(countSubstr(s, k))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation to count the
// subStrings whose decimal equivalent
// is greater than or equal to K
using System;
 
class GFG{
   
// Function to count number of
// subString whose decimal equivalent
// is greater than or equal to K
static long countSubstr(
    String s, int k)
{
   
    int n = s.Length;
   
    // Left pointer of the subString
    int l = n - 1;
   
    // Right pointer of the subString
    int r = n - 1;
    int []arr = new int[n];
    int last_indexof1 = -1;
   
    // Loop to maintain the last
    // occurrence of the 1 in the String
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            arr[i] = i;
            last_indexof1 = i;
        }
        else {
            arr[i] = last_indexof1;
        }
    }
   
    // Variable to count the subString
    long no_of_substr = 0;
   
    // Loop to maintain the every
    // possible end index of the subString
    for (r = n - 1; r >= 0; r--) {
        l = r;
   
        // Loop to find the subString
        // whose decimal equivalent is
        // greater than or equal to K
        while (l >= 0
               && (r - l + 1) <= 64 && (int)(Convert.ToInt32(s.Substring(l, r + 1-l), 2))
                      < k) {
            l--;
        }
   
        // Condition to check no
        // of bits is out of bound
        if (r - l + 1 <= 64)
            no_of_substr += l + 1;
        else {
            no_of_substr += arr[l + 1] + 1;
        }
    }
    return no_of_substr;
}
   
// Driver Code
public static void Main(String[] args)
{
    String s = "11100";
    int k = 3;
    Console.WriteLine(countSubstr(s, k));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript implementation to count the
// subStrings whose decimal equivalent
// is greater than or equal to K
 
// Function to count number of
// subString whose decimal equivalent
// is greater than or equal to K
function countSubstr(s,k)
{
    let n = s.length;
    
    // Left pointer of the subString
    let l = n - 1;
    
    // Right pointer of the subString
    let r = n - 1;
    let arr = new Array(n);
    let last_indexof1 = -1;
    
    // Loop to maintain the last
    // occurrence of the 1 in the String
    for (let i = 0; i < n; i++) {
        if (s[i] == '1') {
            arr[i] = i;
            last_indexof1 = i;
        }
        else {
            arr[i] = last_indexof1;
        }
    }
    
    // Variable to count the subString
    let no_of_substr = 0;
    
    // Loop to maintain the every
    // possible end index of the subString
    for (r = n - 1; r >= 0; r--) {
        l = r;
    
        // Loop to find the subString
        // whose decimal equivalent is
        // greater than or equal to K
        while (l >= 0
               && (r - l + 1) <= 64
               && parseInt(s.substring(l, r + 1),2)
                      < k) {
            l--;
        }
    
        // Condition to check no
        // of bits is out of bound
        if (r - l + 1 <= 64)
            no_of_substr += l + 1;
        else {
            no_of_substr += arr[l + 1] + 1;
        }
    }
    return no_of_substr;
}
 
// Driver Code
let s = "11100";
let k = 3;
document.write(countSubstr(s, k));
 
 
 
// This code is contributed by unknown2108
</script>
Producción: 

8

 

Publicación traducida automáticamente

Artículo escrito por VikashKumr 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 *