Número mínimo de potencias distintas de 2 requeridas para expresar un número binario dado

Dada una string binaria S , la tarea es encontrar el número mínimo de potencias de 2 requeridas para expresar una S.
Ejemplos: 
 

Entrada: S = “111” 
Salida: 2 
Explicación: 
Dos representaciones posibles de “111” (= 7) usando potencias de 2 son: 
2 ⁰ + 2 ¹ + 2 ² = 1 + 2 + 4 = 7 
2 ³ – 2 ⁰ = 8 – 1 = 7 
Por lo tanto, las potencias mínimas de 2 requeridas para representar S son 2.
Entrada: S = “1101101” 
Salida: 4 
Explicación: 
1101101 se puede representar como 2 ⁷ – 2 ⁴ – 2 ² + 2 ⁰ .

Enfoque: 
La observación clave para resolver este problema es que podemos reemplazar cualquier secuencia consecutiva de 1 usando solo dos potencias de 2 . 
 

Ilustración: 
S = “1001110” 
La secuencia de 3 1 consecutivos, “1110” se puede expresar como 2 ⁴ – 2 ¹ 
Por lo tanto, la string dada

Siga los pasos a continuación para resolver el problema: 
 

• Invierta la string S .
• Iterar sobre la string S .
• Reemplace cada substring de 1 que se encuentra dentro de los índices [L, R] colocando 1 en R+1 y -1 en L .
• Una vez que se atraviesa toda la string, cuente el número de valores distintos de cero en la string como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ Program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum
// distinct powers of 2 required
// to express s
void findMinimum(string s)
{
    int n = s.size();
 
    int x[n + 1] = { 0 };
 
    // Reverse the string to
    // start from lower powers
    reverse(s.begin(), s.end());
 
    for (int i = 0; i < n; i++) {
 
        // Check if the character is 1
        if (s[i] == '1') {
 
            if (x[i] == 1) {
                x[i + 1] = 1;
                x[i] = 0;
            }
 
            // Add in range provided range
            else if (i and x[i - 1] == 1) {
                x[i + 1] = 1;
                x[i - 1] = -1;
            }
 
            else
                x[i] = 1;
        }
    }
 
    // Initialize the counter
    int c = 0;
 
    for (int i = 0; i <= n; i++) {
 
        // Check if the character
        // is not 0
        if (x[i] != 0)
 
            // Increment the counter
            c++;
    }
 
    // Print the result
    cout << c << endl;
}
 
// Driver Code
int main()
{
    string str = "111";
 
    findMinimum(str);
 
    return 0;
}

// Java program to implement the
// above approach
import java.util.*;
 
class GFG{
 
// Function to return the minimum
// distinct powers of 2 required
// to express s
static void findMinimum(String s)
{
    int n = s.length();
    int[] x = new int[n + 1];
     
    StringBuilder s2 = new StringBuilder(s);
     
    // Reverse the string to
    // start from lower powers
    s2.reverse();
     
    String s3 = s2.toString();
 
    for(int i = 0; i < n; i++)
    {
 
        // Check if the character is 1
        if (s3.charAt(i) == '1')
        {
            if (x[i] == 1)
            {
                x[i + 1] = 1;
                x[i] = 0;
            }
 
            // Add in range provided range
            else if (1 <= i && (i & x[i - 1]) == 1)
            {
                x[i + 1] = 1;
                x[i - 1] = -1;
            }
            else
                x[i] = 1;
        }
    }
 
    // Initialize the counter
    int c = 0;
 
    for(int i = 0; i <= n; i++)
    {
 
        // Check if the character
        // is not 0
        if (x[i] != 0)
 
            // Increment the counter
            c++;
    }
     
    // Print the result
    System.out.println(c);
}
 
// Driver code
public static void main(String[] args)
{
    String str = "111";
 
    findMinimum(str);
}
}
 
// This code is contributed by offbeat

# Python3 program to implement the
# above approach
 
# Function to return the minimum
# distinct powers of 2 required
# to express s
def findMinimum(s):
 
    n = len(s)
    x = [0] * (n + 1)
 
    # Reverse the string to
    # start from lower powers
    s = s[::-1]
     
    for i in range(n):
         
        # Check if the character is 1
        if(s[i] == '1'):
            if(x[i] == 1):
                x[i + 1] = 1
                x[i] = 0
 
            # Add in range provided range
            elif(i and x[i - 1] == 1):
                x[i + 1] = 1
                x[i - 1] = -1
 
            else:
                x[i] = 1
 
    # Initialize the counter
    c = 0
 
    for i in range(n + 1):
 
        # Check if the character
        # is not 0
        if(x[i] != 0):
 
            # Increment the counter
            c += 1
 
    # Print the result
    print(c)
 
# Driver Code
if __name__ == '__main__':
 
    str = "111"
     
    # Function Call
    findMinimum(str)
 
# This code is contributed by Shivam Singh

// C# program to implement the
// above approach
using System;
using System.Text;
 
class GFG{
 
// Function to return the minimum
// distinct powers of 2 required
// to express s
static void findMinimum(String s)
{
    int n = s.Length;
    int[] x = new int[n + 1];
     
    StringBuilder s2 = new StringBuilder(s);
     
    // Reverse the string to
    // start from lower powers
    s2 = reverse(s2.ToString());
     
    String s3 = s2.ToString();
 
    for(int i = 0; i < n; i++)
    {
         
        // Check if the character is 1
        if (s3[i] == '1')
        {
            if (x[i] == 1)
            {
                x[i + 1] = 1;
                x[i] = 0;
            }
 
            // Add in range provided range
            else if (1 <= i && (i & x[i - 1]) == 1)
            {
                x[i + 1] = 1;
                x[i - 1] = -1;
            }
            else
                x[i] = 1;
        }
    }
 
    // Initialize the counter
    int c = 0;
 
    for(int i = 0; i <= n; i++)
    {
         
        // Check if the character
        // is not 0
        if (x[i] != 0)
 
            // Increment the counter
            c++;
    }
     
    // Print the result
    Console.WriteLine(c);
}
 
static StringBuilder reverse(String input)
{
    char[] a = input.ToCharArray();
    int l, r = a.Length - 1;
     
    for(l = 0; l < r; l++, r--)
    {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return new StringBuilder(String.Join("", a));
}
 
// Driver code
public static void Main(String[] args)
{
    String str = "111";
 
    findMinimum(str);
}
}
 
// This code is contributed by Rohit_ranjan

<script>
  
 
// Javascript Program to implement the
// above approach
 
// Function to return the minimum
// distinct powers of 2 required
// to express s
function findMinimum(s)
{
    var n = s.length;
 
    var x = Array(n+1).fill(0);
 
    // Reverse the string to
    // start from lower powers
    s.reverse();
 
    for (var i = 0; i < n; i++) {
 
        // Check if the character is 1
        if (s[i] == '1') {
 
            if (x[i] == 1) {
                x[i + 1] = 1;
                x[i] = 0;
            }
 
            // Add in range provided range
            else if (i && x[i - 1] == 1) {
                x[i + 1] = 1;
                x[i - 1] = -1;
            }
 
            else
                x[i] = 1;
        }
    }
 
    // Initialize the counter
    var c = 0;
 
    for (var i = 0; i <= n; i++) {
 
        // Check if the character
        // is not 0
        if (x[i] != 0)
 
            // Increment the counter
            c++;
    }
 
    // Print the result
    document.write( c );
}
 
// Driver Code
var str = "111".split('');
findMinimum(str);
 
</script>

2

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)