Dada una string binaria S , la tarea es contar el número mínimo de saltos requeridos para agrupar todos los 1 juntos.
Ejemplos:
Entrada: S = “000010011000100”
Salida: 5
Explicación:
0000 1 0011000100 -> 000000111000100 requiere 2 saltos.
000000111000 1 00 -> 000000111100000 requiere 3 saltos.
Por lo tanto, se requieren al menos 5 saltos para agrupar todos los 1 juntos.Entrada: S = “100010001”
Salida: 6
Explicación:
1 00010001 -> 000 1 10001 requiere 3 saltos.
00011000 1 -> 00011 1 000 requiere 3 saltos.
Enfoque:
podemos observar que para minimizar la cantidad de saltos necesarios para agrupar todos los 1, deben agruparse cerca de la mediana de sus posiciones actuales. Calcule la mediana y el número de movimientos necesarios para cambiar los 1 a la posición más cercana de 0 a la izquierda de la mediana . Realice la misma operación para la derecha de la mediana .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the minimum
// number of jumps required to
// group all ones together in
// the binary string
#include <bits/stdc++.h>
using namespace std;
// Function to get the
// minimum jump value
int getMinJumps(string s)
{
// Store all indices
// of ones
vector<int> ones;
int jumps = 0, median = 0, ind = 0;
// Populating one's indices
for (int i = 0; i < s.length(); i++) {
if (s[i] == '1')
ones.push_back(i);
}
if (ones.size() == 0)
return jumps;
// Calculate median
median = ones[ones.size() / 2];
ind = median;
// Jumps required for 1's
// to the left of median
for (int i = ind; i >= 0; i--) {
if (s[i] == '1') {
jumps += ind - i;
ind--;
}
}
ind = median;
// Jumps required for 1's
// to the right of median
for (int i = ind; i < s.length(); i++) {
if (s[i] == '1') {
jumps += i - ind;
ind++;
}
}
// Return the final answer
return jumps;
}
// Driver Code
int main()
{
string S = "00100000010011";
cout << getMinJumps(S) << '\n';
return 0;
}
Java
// Java Program to find the minimum
// number of jumps required to
// group all ones together in
// the binary string
import java.io.*;
import java.util.*;
class GFG{
// Function to get the
// minimum jump value
public static int getMinJumps(String s)
{
// Store all indices
// of ones
Vector<Integer> ones = new Vector<Integer>();
int jumps = 0, median = 0, ind = 0;
// Populating one's indices
for(int i = 0; i < s.length(); i++)
{
if (s.charAt(i) == '1')
ones.add(i);
}
if (ones.size() == 0)
return jumps;
// Calculate median
median = (int)ones.get(ones.size() / 2);
ind = median;
// Jumps required for 1's
// to the left of median
for(int i = ind; i >= 0; i--)
{
if (s.charAt(i) == '1')
{
jumps += ind - i;
ind--;
}
}
ind = median;
// Jumps required for 1's
// to the right of median
for(int i = ind; i < s.length(); i++)
{
if (s.charAt(i) == '1')
{
jumps += i - ind;
ind++;
}
}
// Return the final answer
return jumps;
}
// Driver code
public static void main(String[] args)
{
String S = "00100000010011";
System.out.println(getMinJumps(S));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to find the minimum # number of jumps required to group # all ones together in the binary string # Function to get the # minimum jump value def getMinJumps(s): # Store all indices # of ones ones = [] jumps, median, ind = 0, 0, 0 # Populating one's indices for i in range(len(s)): if(s[i] == '1'): ones.append(i) if(len(ones) == 0): return jumps # Calculate median median = ones[len(ones) // 2] ind = median # Jumps required for 1's # to the left of median for i in range(ind, -1, -1): if(s[i] == '1'): jumps += ind - i ind -= 1 ind = median # Jumps required for 1's # to the right of median for i in range(ind, len(s)): if(s[i] == '1'): jumps += i - ind ind += 1 # Return the final answer return jumps # Driver Code if __name__ == '__main__': s = "00100000010011" print(getMinJumps(s)) # This code is contributed by Shivam Singh
C#
// C# program to find the minimum
// number of jumps required to
// group all ones together in
// the binary string
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to get the
// minimum jump value
public static int getMinJumps(string s)
{
// Store all indices
// of ones
ArrayList ones = new ArrayList();
int jumps = 0, median = 0, ind = 0;
// Populating one's indices
for(int i = 0; i < s.Length; i++)
{
if (s[i] == '1')
ones.Add(i);
}
if (ones.Count== 0)
return jumps;
// Calculate median
median = (int)ones[ones.Count / 2];
ind = median;
// Jumps required for 1's
// to the left of median
for(int i = ind; i >= 0; i--)
{
if (s[i] == '1')
{
jumps += ind - i;
ind--;
}
}
ind = median;
// Jumps required for 1's
// to the right of median
for(int i = ind; i < s.Length; i++)
{
if (s[i] == '1')
{
jumps += i - ind;
ind++;
}
}
// Return the final answer
return jumps;
}
// Driver code
public static void Main(string[] args)
{
string S = "00100000010011";
Console.Write(getMinJumps(S));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript Program to find the minimum
// number of jumps required to
// group all ones together in
// the binary string
// Function to get the
// minimum jump value
function getMinJumps(s)
{
// Store all indices
// of ones
let ones = [];
let jumps = 0, median = 0, ind = 0;
// Populating one's indices
for(let i = 0; i < s.length; i++)
{
if (s[i] == '1')
ones.push(i);
}
if (ones.length == 0)
return jumps;
// Calculate median
median = ones[parseInt(ones.length / 2, 10)];
ind = median;
// Jumps required for 1's
// to the left of median
for(let i = ind; i >= 0; i--)
{
if (s[i] == '1')
{
jumps += ind - i;
ind--;
}
}
ind = median;
// Jumps required for 1's
// to the right of median
for(let i = ind; i < s.length; i++)
{
if (s[i] == '1')
{
jumps += i - ind;
ind++;
}
}
// Return the final answer
return jumps;
}
let S = "00100000010011";
document.write(getMinJumps(S));
</script>
Producción:
10
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por AnshulVerma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA