Dada una string binaria S de longitud N , la tarea es obtener S de una string, digamos T , de longitud N que consta solo de ceros, mediante un número mínimo de operaciones. Cada operación implica elegir cualquier índice i de la string S y voltear todos los bits en los índices [i, N – 1] de la string T.
Ejemplos:
Entrada: S = “101”
Salida: 3
Explicación:
“000” -> “111” -> “100” -> “101”.
Por lo tanto, el número mínimo de pasos necesarios es 3.
Entrada: S = “10111”
Salida: 3
Explicación:
“00000” -> “11111” -> “10000” -> “10111”.
Por lo tanto, el número mínimo de pasos necesarios es de 3.
Enfoque:
La idea es encontrar la primera aparición de 1 en la string S dada y realizar la operación dada en ese índice. Después de este paso, por cada discrepancia en el carácter de S y T en un índice particular, repita la operación.
Siga los pasos a continuación:
- Iterar sobre S y marcar la primera aparición de 1 .
- Inicialice dos variables, digamos last y ans , donde last almacena el carácter ( 0 o 1 ) para el que se realizó la última operación y ans lleva la cuenta del número mínimo de pasos necesarios.
- Iterar desde la primera aparición de 1 hasta el final de la string.
- Si el carácter actual es 0 y last = 1 , incremente el conteo de ans y establezca last = 0 .
- De lo contrario, si last = 0 y el carácter actual es 1 , establezca last = 1 .
- Devuelve el valor final de ans .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// number of operations required
// to obtain the string s
int minOperations(string s)
{
int n = s.size();
int pos = -1;
// Iterate the string s
for (int i = 0; i < s.size(); i++) {
// If first occurrence of 1
// is found
if (s[i] == '1') {
// Mark the index
pos = i;
break;
}
}
// Base case: If no 1 occurred
if (pos == -1) {
// No operations required
return 0;
}
// Stores the character
// for which last operation
// was performed
int last = 1;
// Stores minimum number
// of operations
int ans = 1;
// Iterate from pos to n
for (int i = pos + 1; i < n; i++) {
// Check if s[i] is 0
if (s[i] == '0') {
// Check if last operation was
// performed because of 1
if (last == 1) {
ans++;
// Set last to 0
last = 0;
}
}
else {
if (last == 0) {
// Check if last operation was
// performed because of 0
ans++;
// Set last to 1
last = 1;
}
}
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
string s = "10111";
cout << minOperations(s);
return 0;
}
Java
// Java program to implement the
// above approach
import java.util.*;
class GFG{
// Function to find the minimum
// number of operations required
// to obtain the string s
static int minOperations(String s)
{
int n = s.length();
int pos = -1;
// Iterate the string s
for(int i = 0; i < s.length(); i++)
{
// If first occurrence of 1
// is found
if (s.charAt(i) == '1')
{
// Mark the index
pos = i;
break;
}
}
// Base case: If no 1 occurred
if (pos == -1)
{
// No operations required
return 0;
}
// Stores the character
// for which last operation
// was performed
int last = 1;
// Stores minimum number
// of operations
int ans = 1;
// Iterate from pos to n
for(int i = pos + 1; i < n; i++)
{
// Check if s[i] is 0
if (s.charAt(i) == '0')
{
// Check if last operation was
// performed because of 1
if (last == 1)
{
ans++;
// Set last to 0
last = 0;
}
}
else
{
if (last == 0)
{
// Check if last operation was
// performed because of 0
ans++;
// Set last to 1
last = 1;
}
}
}
// Return the answer
return ans;
}
// Driver code
public static void main(String[] args)
{
String s = "10111";
System.out.println(minOperations(s));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach # Function to find the minimum # number of operations required # to obtain the string s def minOperations(s): n = len(s) pos = -1 # Iterate the string s for i in range(len(s)): # If first occurrence of 1 # is found if (s[i] == '1'): # Mark the index pos = i break # Base case: If no 1 occurred if (pos == -1): # No operations required return 0 # Stores the character # for which last operation # was performed last = 1 # Stores minimum number # of operations ans = 1 # Iterate from pos to n for i in range(pos + 1, n): # Check if s[i] is 0 if (s[i] == '0'): # Check if last operation was # performed because of 1 if (last == 1): ans += 1 # Set last to 0 last = 0 else: if (last == 0): # Check if last operation was # performed because of 0 ans += 1 # Set last to 1 last = 1 # Return the answer return ans # Driver Code if __name__ == "__main__": s = "10111" print(minOperations(s)) # This code is contributed by chitranayal
C#
// C# program to implement the
// above approach
using System;
class GFG{
// Function to find the minimum
// number of operations required
// to obtain the string s
static int minOperations(String s)
{
int n = s.Length;
int pos = -1;
// Iterate the string s
for(int i = 0; i < s.Length; i++)
{
// If first occurrence of 1
// is found
if (s[i] == '1')
{
// Mark the index
pos = i;
break;
}
}
// Base case: If no 1 occurred
if (pos == -1)
{
// No operations required
return 0;
}
// Stores the character
// for which last operation
// was performed
int last = 1;
// Stores minimum number
// of operations
int ans = 1;
// Iterate from pos to n
for(int i = pos + 1; i < n; i++)
{
// Check if s[i] is 0
if (s[i] == '0')
{
// Check if last operation was
// performed because of 1
if (last == 1)
{
ans++;
// Set last to 0
last = 0;
}
}
else
{
if (last == 0)
{
// Check if last operation was
// performed because of 0
ans++;
// Set last to 1
last = 1;
}
}
}
// Return the answer
return ans;
}
// Driver code
public static void Main(string[] args)
{
String s = "10111";
Console.Write(minOperations(s));
}
}
// This code is contributed by rock_cool
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to find the minimum
// number of operations required
// to obtain the string s
function minOperations(s)
{
let n = s.length;
let pos = -1;
// Iterate the string s
for (let i = 0; i < s.length; i++) {
// If first occurrence of 1
// is found
if (s[i] == '1') {
// Mark the index
pos = i;
break;
}
}
// Base case: If no 1 occurred
if (pos == -1) {
// No operations required
return 0;
}
// Stores the character
// for which last operation
// was performed
let last = 1;
// Stores minimum number
// of operations
let ans = 1;
// Iterate from pos to n
for (let i = pos + 1; i < n; i++) {
// Check if s[i] is 0
if (s[i] == '0') {
// Check if last operation was
// performed because of 1
if (last == 1) {
ans++;
// Set last to 0
last = 0;
}
}
else {
if (last == 0) {
// Check if last operation was
// performed because of 0
ans++;
// Set last to 1
last = 1;
}
}
}
// Return the answer
return ans;
}
let s = "10111";
document.write(minOperations(s));
// This code is contributed by suresh07.
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mridulkumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA