Dada una string binaria S , la tarea es encontrar la suma de la distancia más corta entre todos los 0 y 1 en la string S dada .
Ejemplos:
Entrada: S = “100100”
Salida: 5
Explicación:
Para el ‘0’ en el índice 1, el ‘1’ más cercano está en el índice 0 a una distancia 1.
Para el ‘0’ en el índice 2, el ‘1’ más cercano está en el índice 3 a una distancia 1.
Para el ‘0’ en el índice 4, el ‘1’ más cercano está en el índice 3 a una distancia 1.
Para el ‘0’ en el índice 5, el ‘1’ más cercano está en el índice 3 a una distancia 2.
Por tanto la suma de las distancias es 1 + 1 + 1 + 2 = 5.Entrada: S = “1111”
Salida: 0
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . La idea es buscar el ‘ 1′ para cada ‘ 0′ que esté más cerca del lado izquierdo. De manera similar, busque el ‘ 1′ para cada ‘0’ que esté más cerca del lado derecho. Finalmente, calcule la suma de las distancias que es mínima para cualquier ‘ 0′ a ‘ 1′ del valor calculado de los lados derecho e izquierdo. Siga los pasos a continuación para resolver el problema dado.
- Inicialice los arreglos prefixDistance(N) , suffixDistance(N) para almacenar la distancia desde la izquierda y la derecha respectivamente.
- Inicialice una variable, digamos cnt = 0 que almacene la distancia entre cualquier ‘ 0′ y el ‘ 1′ más cercano .
- Inicialice una variable, digamos haveOne = false , para marcar el carácter ‘ 1′ .
- Inicialice una variable, digamos suma = 0 que almacene la suma total entre todos los ‘ 0′ hasta su ‘ 1′ más cercano .
- Iterar sobre el rango [0, N – 1] usando la variable i realizar los siguientes pasos:
- Si el valor de S[i] es ‘ 1′, entonces asigne haveOne como true , cnt como 0 y prefixDistance[i] como 0 .
- De lo contrario, si haveOne es verdadero , incremente el valor de cnt en 1 y asigne el valor de prefixDistance[i] como cnt .
- Iterar sobre el rango [0, N – 1] usando la variable i realizar los siguientes pasos:
- Si el valor de S[i] es ‘ 1′, entonces asigne haveOne como true , cnt como 0 y sufijoDistance[i] como 0 .
- De lo contrario, si haveOne es verdadero, incremente el valor de cnt en 1 y asigne el valor de suffixDistance[i] como cnt .
- Iterar sobre el rango [0, N – 1] usando la variable i y si el valor de S[i] es ‘ 1′ entonces actualice la suma como sum += min(prefixDistance[i], suffixDistance[i]) .
- Después de completar los pasos anteriores, imprima el valor de la suma como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the total sum of
// the shortest distance between every
// 0 to 1 in a given binary string
void findTotalDistance(string S, int N)
{
// Stores the prefix distance and
// suffix distance from 0 to 1
vector<int> prefixDistance(N);
vector<int> suffixDistance(N);
// Stores the current distance
// from 1 to 0
int cnt = 0;
// Marks the 1
bool haveOne = false;
for (int i = 0; i < N; ++i) {
// If current character is 1
if (S[i] == '1') {
// Mark haveOne to true
haveOne = true;
// Assign the cnt to 0
cnt = 0;
// Assign prefixDistance[i] as 0
prefixDistance[i] = 0;
}
// If haveOne is true
else if (haveOne) {
// Update the cnt
cnt++;
// Update prefixDistance[i]
prefixDistance[i] = cnt;
}
// Assign prefixDistance[i]
// as INT_MAX
else
prefixDistance[i] = INT_MAX;
}
// Assign haveOne as false
haveOne = false;
for (int i = N - 1; i >= 0; --i) {
// If current character is 1
if (S[i] == '1') {
// Mark haveOne to true
haveOne = true;
// Assign the cnt to 0
cnt = 0;
// Assign the suffixDistance[i]
// as 0
suffixDistance[i] = 0;
}
// If haveOne is true
else if (haveOne) {
// Update the cnt
cnt++;
// Update suffixDistance[i]
// as cnt
suffixDistance[i] = cnt;
}
else
// Assign suffixDistance[i]
// as INT_MAX
suffixDistance[i] = INT_MAX;
}
// Stores the total sum of distances
// between 0 to nearest 1
int sum = 0;
for (int i = 0; i < N; ++i) {
// If current character is 0
if (S[i] == '0') {
// Update the value of sum
sum += min(prefixDistance[i],
suffixDistance[i]);
}
}
// Print the value of the sum
cout << sum << endl;
}
// Driver Code
int main()
{
string S = "100100";
int N = S.length();
findTotalDistance(S, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
public class GFG{
// Function to find the total sum of
// the shortest distance between every
// 0 to 1 in a given binary string
static void findTotalDistance(String S, int N)
{
// Stores the prefix distance and
// suffix distance from 0 to 1
int []prefixDistance = new int[N];
int []suffixDistance = new int[N];
// Stores the current distance
// from 1 to 0
int cnt = 0;
// Marks the 1
boolean haveOne = false;
for (int i = 0; i < N; ++i) {
// If current character is 1
if (S.charAt(i) == '1') {
// Mark haveOne to true
haveOne = true;
// Assign the cnt to 0
cnt = 0;
// Assign prefixDistance[i] as 0
prefixDistance[i] = 0;
}
// If haveOne is true
else if (haveOne) {
// Update the cnt
cnt++;
// Update prefixDistance[i]
prefixDistance[i] = cnt;
}
// Assign prefixDistance[i]
// as INT_MAX
else
prefixDistance[i] = Integer.MAX_VALUE;
}
// Assign haveOne as false
haveOne = false;
for (int i = N - 1; i >= 0; --i) {
// If current character is 1
if (S.charAt(i) == '1') {
// Mark haveOne to true
haveOne = true;
// Assign the cnt to 0
cnt = 0;
// Assign the suffixDistance[i]
// as 0
suffixDistance[i] = 0;
}
// If haveOne is true
else if (haveOne) {
// Update the cnt
cnt++;
// Update suffixDistance[i]
// as cnt
suffixDistance[i] = cnt;
}
else
// Assign suffixDistance[i]
// as INT_MAX
suffixDistance[i] = Integer.MAX_VALUE;
}
// Stores the total sum of distances
// between 0 to nearest 1
int sum = 0;
for (int i = 0; i < N; ++i) {
// If current character is 0
if (S.charAt(i) == '0') {
// Update the value of sum
sum += Math.min(prefixDistance[i],
suffixDistance[i]);
}
}
// Print the value of the sum
System.out.print(sum);
}
// Driver Code
public static void main(String []args)
{
String S = "100100";
int N = S.length();
findTotalDistance(S, N);
}
}
// This code is contributed by AnkThon
Python3
# python program for the above approach # Function to find the total sum of # the shortest distance between every # 0 to 1 in a given binary string INT_MAX = 2147483647 def findTotalDistance(S, N): # Stores the prefix distance and # suffix distance from 0 to 1 prefixDistance = [0 for _ in range(N)] suffixDistance = [0 for _ in range(N)] # Stores the current distance # from 1 to 0 cnt = 0 # Marks the 1 haveOne = False for i in range(0, N): # If current character is 1 if (S[i] == '1'): # // Mark haveOne to true haveOne = True # Assign the cnt to 0 cnt = 0 # Assign prefixDistance[i] as 0 prefixDistance[i] = 0 # If haveOne is true elif (haveOne): # Update the cnt cnt = cnt + 1 # Update prefixDistance[i] prefixDistance[i] = cnt # Assign prefixDistance[i] # as INT_MAX else: prefixDistance[i] = INT_MAX # Assign haveOne as false haveOne = False for i in range(N-1, -1, -1): # If current character is 1 if (S[i] == '1'): # Mark haveOne to true haveOne = True # Assign the cnt to 0 cnt = 0 # Assign the suffixDistance[i] # as 0 suffixDistance[i] = 0 # If haveOne is true elif (haveOne): # Update the cnt cnt = cnt + 1 # Update suffixDistance[i] # as cnt suffixDistance[i] = cnt else: # // Assign suffixDistance[i] # // as INT_MAX suffixDistance[i] = INT_MAX # Stores the total sum of distances # between 0 to nearest 1 sum = 0 for i in range(0, N): # If current character is 0 if (S[i] == '0'): # Update the value of sum sum += min(prefixDistance[i], suffixDistance[i]) # Print the value of the sum print(sum) # Driver Code if __name__ == "__main__": S = "100100" N = len(S) findTotalDistance(S, N) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the total sum of
// the shortest distance between every
// 0 to 1 in a given binary string
static void findTotalDistance(string S, int N)
{
// Stores the prefix distance and
// suffix distance from 0 to 1
int []prefixDistance = new int[N];
int []suffixDistance = new int[N];
// Stores the current distance
// from 1 to 0
int cnt = 0;
// Marks the 1
bool haveOne = false;
for (int i = 0; i < N; ++i) {
// If current character is 1
if (S[i] == '1') {
// Mark haveOne to true
haveOne = true;
// Assign the cnt to 0
cnt = 0;
// Assign prefixDistance[i] as 0
prefixDistance[i] = 0;
}
// If haveOne is true
else if (haveOne) {
// Update the cnt
cnt++;
// Update prefixDistance[i]
prefixDistance[i] = cnt;
}
// Assign prefixDistance[i]
// as INT_MAX
else
prefixDistance[i] = Int32.MaxValue;
}
// Assign haveOne as false
haveOne = false;
for (int i = N - 1; i >= 0; --i) {
// If current character is 1
if (S[i] == '1') {
// Mark haveOne to true
haveOne = true;
// Assign the cnt to 0
cnt = 0;
// Assign the suffixDistance[i]
// as 0
suffixDistance[i] = 0;
}
// If haveOne is true
else if (haveOne) {
// Update the cnt
cnt++;
// Update suffixDistance[i]
// as cnt
suffixDistance[i] = cnt;
}
else
// Assign suffixDistance[i]
// as INT_MAX
suffixDistance[i] = Int32.MaxValue;
}
// Stores the total sum of distances
// between 0 to nearest 1
int sum = 0;
for (int i = 0; i < N; ++i) {
// If current character is 0
if (S[i] == '0') {
// Update the value of sum
sum += Math.Min(prefixDistance[i],
suffixDistance[i]);
}
}
// Print the value of the sum
Console.Write(sum);
}
// Driver Code
public static void Main()
{
string S = "100100";
int N = S.Length;
findTotalDistance(S, N);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach
const INT_MAX = 2147483647
// Function to find the total sum of
// the shortest distance between every
// 0 to 1 in a given binary string
const findTotalDistance = (S, N) => {
// Stores the prefix distance and
// suffix distance from 0 to 1
let prefixDistance = new Array(N).fill(0);
let suffixDistance = new Array(N).fill(0);
// Stores the current distance
// from 1 to 0
let cnt = 0;
// Marks the 1
let haveOne = false;
for (let i = 0; i < N; ++i) {
// If current character is 1
if (S[i] == '1') {
// Mark haveOne to true
haveOne = true;
// Assign the cnt to 0
cnt = 0;
// Assign prefixDistance[i] as 0
prefixDistance[i] = 0;
}
// If haveOne is true
else if (haveOne) {
// Update the cnt
cnt++;
// Update prefixDistance[i]
prefixDistance[i] = cnt;
}
// Assign prefixDistance[i]
// as INT_MAX
else
prefixDistance[i] = INT_MAX;
}
// Assign haveOne as false
haveOne = false;
for (let i = N - 1; i >= 0; --i) {
// If current character is 1
if (S[i] == '1') {
// Mark haveOne to true
haveOne = true;
// Assign the cnt to 0
cnt = 0;
// Assign the suffixDistance[i]
// as 0
suffixDistance[i] = 0;
}
// If haveOne is true
else if (haveOne) {
// Update the cnt
cnt++;
// Update suffixDistance[i]
// as cnt
suffixDistance[i] = cnt;
}
else
// Assign suffixDistance[i]
// as INT_MAX
suffixDistance[i] = INT_MAX;
}
// Stores the total sum of distances
// between 0 to nearest 1
let sum = 0;
for (let i = 0; i < N; ++i) {
// If current character is 0
if (S[i] == '0') {
// Update the value of sum
sum += Math.min(prefixDistance[i], suffixDistance[i]);
}
}
// Print the value of the sum
document.write(`${sum}<br/>`);
}
// Driver Code
let S = "100100";
let N = S.length;
findTotalDistance(S, N);
// This code is contributed by rakeshsahni
</script>
Producción:
5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA