Dado un número binario como una string str de longitud L . La tarea es encontrar el número mínimo de operaciones necesarias para que el número se convierta en 2 L -1 , que es una string que consta de solo 1 de longitud L .
En cada operación, el número N puede ser reemplazado por N x o (N + 1) .
Ejemplos:
Entrada: str = “10010111”
Salida: 5
N = 10010111, N + 1 = 10011000, entonces N xor (N + 1) = 00001111
N = 00001111, N + 1 = 00010000, entonces N xor (N + 1) = 00011111
N = 00011111, N + 1 = 00100000, entonces N xor (N + 1) = 00111111
N = 00111111, N + 1 = 01000000, entonces N xor (N + 1) = 01111111
N = 01111111, N + 1 = 10000000, entonces N xor (N + 1) = 11111111
Entrada: str = “101000100101011101”
Salida: 17
Planteamiento: Después de realizar la operación dada, se puede observar que para obtener el número requerido, al final, el número de operaciones será:
Número de operaciones = longitud de la string (después de eliminar los 0 iniciales) – recuento de 1 consecutivos desde el final (comenzando desde el bit menos significativo)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number
// of operations required
int changeToOnes(string str)
{
// ctr will store the number of
// consecutive ones at the end
// of the given binary string
int i, l, ctr = 0;
l = str.length();
// Loop to find number of 1s
// at the end of the string
for (i = l - 1; i >= 0; i--) {
// If the current character is 1
if (str[i] == '1')
ctr++;
// If we encounter the first 0
// from the LSB position then
// we'll break the loop
else
break;
}
// Number of operations
// required is (l - ctr)
return l - ctr;
}
// Function to remove leading
// zeroes from the string
string removeZeroesFromFront(string str)
{
string s;
int i = 0;
// Loop until s[i] becomes
// not equal to 1
while (i < str.length() && str[i] == '0')
i++;
// If we reach the end of
// the string, it means that
// string contains only 0's
if (i == str.length())
s = "0";
// Return the string without
// leading zeros
else
s = str.substr(i, str.length() - i);
return s;
}
// Driver code
int main()
{
string str = "10010111";
// Removing the leading zeroes
str = removeZeroesFromFront(str);
cout << changeToOnes(str);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the number
// of operations required
static int changeToOnes(String str)
{
// ctr will store the number of
// consecutive ones at the end
// of the given binary string
int i, l, ctr = 0;
l = str.length();
// Loop to find number of 1s
// at the end of the string
for (i = l - 1; i >= 0; i--)
{
// If the current character is 1
if (str.charAt(i) == '1')
ctr++;
// If we encounter the first 0
// from the LSB position then
// we'll break the loop
else
break;
}
// Number of operations
// required is (l - ctr)
return l - ctr;
}
// Function to remove leading
// zeroes from the string
static String removeZeroesFromFront(String str)
{
String s;
int i = 0;
// Loop until s[i] becomes
// not equal to 1
while (i < str.length() &&
str.charAt(i) == '0')
i++;
// If we reach the end of
// the string, it means that
// string contains only 0's
if (i == str.length())
s = "0";
// Return the string without
// leading zeros
else
s = str.substring(i, str.length() - i);
return s;
}
// Driver code
public static void main(String[] args)
{
String str = "10010111";
// Removing the leading zeroes
str = removeZeroesFromFront(str);
System.out.println(changeToOnes(str));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Function to return the number # of operations required def changeToOnes(string) : # ctr will store the number of # consecutive ones at the end # of the given binary string ctr = 0; l = len(string); # Loop to find number of 1s # at the end of the string for i in range(l - 1, -1, -1) : # If the current character is 1 if (string[i] == '1') : ctr += 1; # If we encounter the first 0 # from the LSB position then # we'll break the loop else : break; # Number of operations # required is (l - ctr) return l - ctr; # Function to remove leading # zeroes from the string def removeZeroesFromFront(string) : s = ""; i = 0; # Loop until s[i] becomes # not equal to 1 while (i < len(string) and string[i] == '0') : i += 1; # If we reach the end of # the string, it means that # string contains only 0's if (i == len(string)) : s = "0"; # Return the string without # leading zeros else : s = string[i: len(string) - i]; return s; # Driver code if __name__ == "__main__" : string = "10010111"; # Removing the leading zeroes string = removeZeroesFromFront(string); print(changeToOnes(string)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the number
// of operations required
static int changeToOnes(String str)
{
// ctr will store the number of
// consecutive ones at the end
// of the given binary string
int i, l, ctr = 0;
l = str.Length;
// Loop to find number of 1s
// at the end of the string
for (i = l - 1; i >= 0; i--)
{
// If the current character is 1
if (str[i] == '1')
ctr++;
// If we encounter the first 0
// from the LSB position then
// we'll break the loop
else
break;
}
// Number of operations
// required is (l - ctr)
return l - ctr;
}
// Function to remove leading
// zeroes from the string
static String removeZeroesFromFront(String str)
{
String s;
int i = 0;
// Loop until s[i] becomes
// not equal to 1
while (i < str.Length &&
str[i] == '0')
i++;
// If we reach the end of
// the string, it means that
// string contains only 0's
if (i == str.Length)
s = "0";
// Return the string without
// leading zeros
else
s = str.Substring(i, str.Length - i);
return s;
}
// Driver code
public static void Main(String[] args)
{
String str = "10010111";
// Removing the leading zeroes
str = removeZeroesFromFront(str);
Console.WriteLine(changeToOnes(str));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the number
// of operations required
function changeToOnes(str)
{
// ctr will store the number of
// consecutive ones at the end
// of the given binary string
var i, l, ctr = 0;
l = str.length;
// Loop to find number of 1s
// at the end of the string
for (i = l - 1; i >= 0; i--) {
// If the current character is 1
if (str[i] == '1')
ctr++;
// If we encounter the first 0
// from the LSB position then
// we'll break the loop
else
break;
}
// Number of operations
// required is (l - ctr)
return l - ctr;
}
// Function to remove leading
// zeroes from the string
function removeZeroesFromFront(str)
{
var s;
var i = 0;
// Loop until s[i] becomes
// not equal to 1
while (i < str.length && str[i] == '0')
i++;
// If we reach the end of
// the string, it means that
// string contains only 0's
if (i == str.length)
s = "0";
// Return the string without
// leading zeros
else
s = str.substring(i, str.length - i);
return s;
}
// Driver code
var str = "10010111";
// Removing the leading zeroes
str = removeZeroesFromFront(str);
document.write( changeToOnes(str));
</script>
Producción:
5
Complejidad de tiempo: O(n)