Dada una string binaria, S. Encuentre el número mínimo de operaciones requeridas a realizar sobre el número cero para convertirlo al número representado por S.
Se permite realizar operaciones de 2 tipos:
- Añadir 2x _
- restar 2 x
Nota : Comience a realizar operaciones en 0.
Ejemplos:
Entrada: 100
Salida: 1
Explicación : solo realizamos una sola operación, es decir, sumamos 4 (2^2)Entrada: 111
Salida: 2
Explicación : Realizamos las siguientes dos operaciones:
1) Sumar 8 (2 ^ 3)
2) Restar 1 (2 ^ 0)
La idea es utilizar Programación Dinámica para resolver este problema.
Nota : En el análisis a continuación, consideramos que todas las strings binarias se representan de LSB a MSB (de LHS a RHS), es decir, 2 (forma binaria: «10») se representa como «01».
Sea S la string binaria dada.
Sea dp[i][0] el número mínimo de operaciones requeridas para hacer una string binaria R tal que R[0…i] sea lo mismo que S[0…i] y R[ i+1…] = “00..0”
De manera similar, sea dp[i][1] el número mínimo de operaciones requeridas para hacer una string binaria R tal que R[0…i] sea lo mismo que S[0 …i] y R[i+1…] = “11..1”
Si S ies ‘0’, entonces dp[i][0] = dp[i – 1][0]. Ya que no requerimos ninguna operación adicional. Ahora consideramos el valor de dp[i][1], que es un poco más complicado. Para dp[i][1], podemos hacer nuestra transición de dp[i – 1][1] simplemente haciendo el i -ésimo carácter de la string formada por dp[i-1][1], ‘0’ . Desde antes, el i -ésimo carácter era “1”. Solo necesitamos restar 2 i de la string representada por dp[i-1][0]. Por lo tanto, realizamos una operación diferente a las representadas por dp[i-1][0].
La otra transición podría ser de dp[i-1][0]. Deje que dp[i-1][1] represente la string R. Entonces necesitamos mantener R[i] = 0 como ya está pero R[i + 1…..] que actualmente es “000..0”, debe cambiarse a “111…1”, esto se puede hacer restando 2 (i+1)de R. Por lo tanto, solo necesitamos una operación además de las representadas por dp[i-1][0].
Similar es el caso cuando S i es ‘1’.
La respuesta final es la representada por dp[l-1][0], donde l es la longitud de la string binaria S.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the minimum number
// of operations required to sum to N
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum operations required
// to sum to a number represented by the binary string S
int findMinOperations(string S)
{
// Reverse the string to consider
// it from LSB to MSB
reverse(S.begin(), S.end());
int n = S.length();
// initialise the dp table
int dp[n + 1][2];
// If S[0] = '0', there is no need to
// perform any operation
if (S[0] == '0') {
dp[0][0] = 0;
}
else {
// If S[0] = '1', just perform a single
// operation(i.e Add 2^0)
dp[0][0] = 1;
}
// Irrespective of the LSB, dp[0][1] is always
// 1 as there is always the need of making the
// suffix of the binary string of the form "11....1"
// as suggested by the definition of dp[i][1]
dp[0][1] = 1;
for (int i = 1; i < n; i++) {
if (S[i] == '0') {
// Transition from dp[i - 1][0]
dp[i][0] = dp[i - 1][0];
/* 1. Transition from dp[i - 1][1] by just doing
1 extra operation of subtracting 2^i
2. Transition from dp[i - 1][0] by just doing
1 extra operation of subtracting 2^(i+1) */
dp[i][1] = 1 + min(dp[i - 1][1], dp[i - 1][0]);
}
else {
// Transition from dp[i - 1][1]
dp[i][1] = dp[i - 1][1];
/* 1. Transition from dp[i - 1][1] by just doing
1 extra operation of adding 2^(i+1)
2. Transition from dp[i - 1][0] by just doing
1 extra operation of adding 2^i */
dp[i][0] = 1 + min(dp[i - 1][0], dp[i - 1][1]);
}
}
return dp[n - 1][0];
}
// Driver Code
int main()
{
string S = "100";
cout << findMinOperations(S) << endl;
S = "111";
cout << findMinOperations(S) << endl;
return 0;
}
Java
// Java program to find the minimum number
// of operations required to sum to N
class GFG
{
// Function to return the minimum operations required
// to sum to a number represented by the binary string S
static int findMinOperations(String S)
{
// Reverse the string to consider
// it from LSB to MSB
S = reverse(S);
int n = S.length();
// initialise the dp table
int dp[][] = new int[n + 1][2];
// If S[0] = '0', there is no need to
// perform any operation
if (S.charAt(0) == '0')
{
dp[0][0] = 0;
}
else
{
// If S[0] = '1', just perform a single
// operation(i.e Add 2^0)
dp[0][0] = 1;
}
// Irrespective of the LSB, dp[0][1] is always
// 1 as there is always the need of making the
// suffix of the binary string of the form "11....1"
// as suggested by the definition of dp[i][1]
dp[0][1] = 1;
for (int i = 1; i < n; i++)
{
if (S.charAt(i) == '0')
{
// Transition from dp[i - 1][0]
dp[i][0] = dp[i - 1][0];
/* 1. Transition from dp[i - 1][1] by just doing
1 extra operation of subtracting 2^i
2. Transition from dp[i - 1][0] by just doing
1 extra operation of subtracting 2^(i+1) */
dp[i][1] = 1 + Math.min(dp[i - 1][1], dp[i - 1][0]);
}
else
{
// Transition from dp[i - 1][1]
dp[i][1] = dp[i - 1][1];
/* 1. Transition from dp[i - 1][1] by just doing
1 extra operation of adding 2^(i+1)
2. Transition from dp[i - 1][0] by just doing
1 extra operation of adding 2^i */
dp[i][0] = 1 + Math.min(dp[i - 1][0], dp[i - 1][1]);
}
}
return dp[n - 1][0];
}
static String reverse(String input)
{
char[] temparray = input.toCharArray();
int left, right = 0;
right = temparray.length - 1;
for (left = 0; left < right; left++, right--)
{
// Swap values of left and right
char temp = temparray[left];
temparray[left] = temparray[right];
temparray[right] = temp;
}
return String.valueOf(temparray);
}
// Driver Code
public static void main(String[] args)
{
String S = "100";
System.out.println(findMinOperations(S));
S = "111";
System.out.println(findMinOperations(S));
}
}
// This code is contributed by
// PrinciRaj1992
Python3
# Python3 program to find the minimum # number of operations required to sum to N # Function to return the minimum # operations required to sum to a # number represented by the binary string S def findMinOperations(S) : # Reverse the string to consider # it from LSB to MSB S = S[: : -1] n = len(S) # initialise the dp table dp = [[0] * 2] * (n + 1) # If S[0] = '0', there is no need # to perform any operation if (S[0] == '0') : dp[0][0] = 0 else : # If S[0] = '1', just perform a # single operation(i.e Add 2^0) dp[0][0] = 1 # Irrespective of the LSB, dp[0][1] is # always 1 as there is always the need # of making the suffix of the binary # string of the form "11....1" as # suggested by the definition of dp[i][1] dp[0][1] = 1 for i in range(1, n) : if (S[i] == '0') : # Transition from dp[i - 1][0] dp[i][0] = dp[i - 1][0] """ 1. Transition from dp[i - 1][1] by just doing 1 extra operation of subtracting 2^i 2. Transition from dp[i - 1][0] by just doing 1 extra operation of subtracting 2^(i+1) """ dp[i][1] = 1 + min(dp[i - 1][1], dp[i - 1][0]) else : # Transition from dp[i - 1][1] dp[i][1] = dp[i - 1][1]; """ 1. Transition from dp[i - 1][1] by just doing 1 extra operation of adding 2^(i+1) 2. Transition from dp[i - 1][0] by just doing 1 extra operation of adding 2^i """ dp[i][0] = 1 + min(dp[i - 1][0], dp[i - 1][1]) return dp[n - 1][0] # Driver Code if __name__ == "__main__" : S = "100" print(findMinOperations(S)) S = "111"; print(findMinOperations(S)) # This code is contributed by Ryuga
C#
// C# program to find the minimum number
// of operations required to sum to N
using System;
class GFG
{
// Function to return the minimum
// operations required to sum
// to a number represented by
// the binary string S
static int findMinOperations(String S)
{
// Reverse the string to consider
// it from LSB to MSB
S = reverse(S);
int n = S.Length;
// initialise the dp table
int [,]dp = new int[n + 1, 2];
// If S[0] = '0', there is no need to
// perform any operation
if (S[0] == '0')
{
dp[0, 0] = 0;
}
else
{
// If S[0] = '1', just perform a single
// operation(i.e Add 2^0)
dp[0, 0] = 1;
}
// Irrespective of the LSB, dp[0,1] is always
// 1 as there is always the need of making the
// suffix of the binary string of the form "11....1"
// as suggested by the definition of dp[i,1]
dp[0, 1] = 1;
for (int i = 1; i < n; i++)
{
if (S[i] == '0')
{
// Transition from dp[i - 1,0]
dp[i, 0] = dp[i - 1, 0];
/* 1. Transition from dp[i - 1,1] by just doing
1 extra operation of subtracting 2^i
2. Transition from dp[i - 1,0] by just doing
1 extra operation of subtracting 2^(i+1) */
dp[i, 1] = 1 + Math.Min(dp[i - 1, 1], dp[i - 1, 0]);
}
else
{
// Transition from dp[i - 1,1]
dp[i, 1] = dp[i - 1, 1];
/* 1. Transition from dp[i - 1,1] by just doing
1 extra operation of adding 2^(i+1)
2. Transition from dp[i - 1,0] by just doing
1 extra operation of adding 2^i */
dp[i, 0] = 1 + Math.Min(dp[i - 1, 0], dp[i - 1, 1]);
}
}
return dp[n - 1, 0];
}
static String reverse(String input)
{
char[] temparray = input.ToCharArray();
int left, right = 0;
right = temparray.Length - 1;
for (left = 0; left < right; left++, right--)
{
// Swap values of left and right
char temp = temparray[left];
temparray[left] = temparray[right];
temparray[right] = temp;
}
return String.Join("",temparray);
}
// Driver Code
public static void Main()
{
String S = "100";
Console.WriteLine(findMinOperations(S));
S = "111";
Console.WriteLine(findMinOperations(S));
}
}
//This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to find the minimum number
// of operations required to sum to N
// Function to return the minimum operations required
// to sum to a number represented by the binary string S
function findMinOperations($S)
{
// Reverse the string to consider
// it from LSB to MSB
$p= strrev($S);
$n = strlen($p);
// initialise the dp table
$dp = array_fill(0,$n + 1,array_fill(0,2,NULL));
// If S[0] = '0', there is no need to
// perform any operation
if ($p[0] == '0') {
$dp[0][0] = 0;
}
else {
// If S[0] = '1', just perform a single
// operation(i.e Add 2^0)
$dp[0][0] = 1;
}
// Irrespective of the LSB, dp[0][1] is always
// 1 as there is always the need of making the
// suffix of the binary string of the form "11....1"
// as suggested by the definition of dp[i][1]
$dp[0][1] = 1;
for ($i = 1; $i < $n; $i++) {
if ($p[$i] == '0') {
// Transition from dp[i - 1][0]
$dp[$i][0] = $dp[$i - 1][0];
/* 1. Transition from dp[i - 1][1] by just doing
1 extra operation of subtracting 2^i
2. Transition from dp[i - 1][0] by just doing
1 extra operation of subtracting 2^(i+1) */
$dp[$i][1] = 1 + min($dp[$i - 1][1], $dp[$i - 1][0]);
}
else {
// Transition from dp[i - 1][1]
$dp[$i][1] = $dp[$i - 1][1];
/* 1. Transition from dp[i - 1][1] by just doing
1 extra operation of adding 2^(i+1)
2. Transition from dp[i - 1][0] by just doing
1 extra operation of adding 2^i */
$dp[$i][0] = 1 + min($dp[$i - 1][0], $dp[$i - 1][1]);
}
}
return $dp[$n - 1][0];
}
// Driver Code
$S = "100";
echo findMinOperations($S)."\n";
$S = "111";
echo findMinOperations($S)."\n";
return 0;
// This code is contributed by Ita_c.
?>
Javascript
<script>
// Javascript program to find the minimum number
// of operations required to sum to N
// Function to return the minimum operations required
// to sum to a number represented by the binary string S
function findMinOperations(S)
{
// Reverse the string to consider
// it from LSB to MSB
S = reverse(S);
let n = S.length;
// initialise the dp table
let dp = new Array(n + 1);
for(let i=0;i<dp.length;i++)
{
dp[i]=new Array(2);
for(let j=0;j<2;j++)
{
dp[i][j]=0;
}
}
// If S[0] = '0', there is no need to
// perform any operation
if (S[0] == '0')
{
dp[0][0] = 0;
}
else
{
// If S[0] = '1', just perform a single
// operation(i.e Add 2^0)
dp[0][0] = 1;
}
// Irrespective of the LSB, dp[0][1] is always
// 1 as there is always the need of making the
// suffix of the binary string of the form "11....1"
// as suggested by the definition of dp[i][1]
dp[0][1] = 1;
for (let i = 1; i < n; i++)
{
if (S[i] == '0')
{
// Transition from dp[i - 1][0]
dp[i][0] = dp[i - 1][0];
/* 1. Transition from dp[i - 1][1] by just doing
1 extra operation of subtracting 2^i
2. Transition from dp[i - 1][0] by just doing
1 extra operation of subtracting 2^(i+1) */
dp[i][1] = 1 + Math.min(dp[i - 1][1], dp[i - 1][0]);
}
else
{
// Transition from dp[i - 1][1]
dp[i][1] = dp[i - 1][1];
/* 1. Transition from dp[i - 1][1] by just doing
1 extra operation of adding 2^(i+1)
2. Transition from dp[i - 1][0] by just doing
1 extra operation of adding 2^i */
dp[i][0] = 1 + Math.min(dp[i - 1][0], dp[i - 1][1]);
}
}
return dp[n - 1][0];
}
function reverse(input)
{
let temparray = input.split("");
let left, right = 0;
right = temparray.length - 1;
for (left = 0; left < right; left++, right--)
{
// Swap values of left and right
let temp = temparray[left];
temparray[left] = temparray[right];
temparray[right] = temp;
}
return (temparray).join("");
}
// Driver Code
let S = "100";
document.write(findMinOperations(S)+"<br>");
S = "111";
document.write(findMinOperations(S)+"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1 2
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)