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» – 3Entrada: 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
- La idea es mantener dos punteros L y R .
- 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