Genere una string binaria de tamaño N con el prefijo S y sea lexicográficamente lo más pequeña posible

Dada una string binaria S , la tarea es crear una string binaria de tamaño N a partir de la string S dada (no cambie la posición de los caracteres) siguiendo las siguientes condiciones:

  • El prefijo de la string es S.
  • Si es lo lexicográficamente más pequeño posible.
  • La diferencia absoluta entre el número de 1 y 0 es mínima.

Ejemplos:

Entrada: S = “101”, N = 8
Salida: 10100011
Explicación: El prefijo de la string de salida es el mismo que el de la string S. 
La diferencia absoluta entre el número de 0 y 1 es 0.
Es la lexicografía más pequeña posible que sigue a todas las condición dada.

Entrada: S = “001”, N = 7
Salida: 0010011 

 

Enfoque: este problema se puede resolver utilizando el enfoque codicioso basado en la siguiente idea:

En el caso de una string binaria, una string que comienza con ‘0’ es lexicográficamente más pequeña que la que comienza con ‘1 ‘.
Entonces, primero haga S el prefijo y luego encuentre cuántos 0 y 1 más se pueden agregar. Para hacerlo lexicográficamente más pequeño, agregue todos los 0 primero y luego los 1. 

Siga los pasos que se mencionan a continuación para implementar el enfoque.

  • Cuente números de 1 y 0 y guárdelos (digamos en count1 y count0 respectivamente).
  • Encuentre la diferencia entre (digamos g ) count0 y count1 y entre N y la longitud de S (digamos en una variable l ).
  • Calcule el tamaño que necesitamos incrementar en la longitud de la string para hacer que la longitud de la string sea = N y guárdelo en l .
  • Ahora agregue tantos 0 s (que serán (lg)/2 ) tales que el número de 0 sea igual a N/2 y luego agregue 1 s para los lugares restantes.

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

C++

#include <iostream>
 
using namespace std;
 
// Function to build string
string find_string(int n, string s)
{
    // Declaring variable
    int count0 = 0, count1 = 0;
 
    // Check number of 1's and 0's
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '0') {
            count0++;
        }
        else {
            count1++;
        }
    }
    string sb = s;
 
    // Store difference in number of 1's
    // and 0's
    int g = count0 - count1;
 
    // l store the value that how much 0's
    // or 1's we need to add in string
    int l = n - s.length();
    l -= g;
 
    // u store the count of
    // number of 0's we need to insert
    int u = l / 2;
    while (u > 0) {
        sb += '0';
        u--;
    }
    if (l % 2 != 0) {
        sb += '0';
    }
 
    while (sb.length() < n) {
        sb += '1';
    }
 
    // Retutrn result
    return sb;
}
 
// Driver code
int main()
{
    int N = 7;
    string S = "001";
 
    // Function call
    cout << find_string(N, S);
}
 
// This code is contributed by phasing17

Java

// Java program for above approach
 
import java.io.*;
import java.lang.*;
 
class GFG {
 
    // Function to build string
    String find_string(int n, String s)
    {
        // Declaring variable
        int count0 = 0, count1 = 0;
 
        // Check number of 1's and 0's
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                count0++;
            }
            else {
                count1++;
            }
        }
        String sb = s;
 
        // Store difference in number of 1's
        // and 0's
        int g = count0 - count1;
 
        // l store the value that how much 0's
        // or 1's we need to add in string
        int l = n - s.length();
        l -= g;
 
        // u store the count of
        // number of 0's we need to insert
        int u = l / 2;
        while (u > 0) {
            sb += '0';
            u--;
        }
        if (l % 2 != 0) {
            sb += '0';
        }
 
        while (sb.length() < n) {
            sb += '1';
        }
 
        // Retutrn result
        return sb;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 7;
        String S = "001";
        GFG g = new GFG();
 
        // Function call
        System.out.println(g.find_string(N, S));
    }
}

Python3

# Python program for above approach
 
# Function to build string
def find_string(n, s):
   
    # Declaring variable
    count0 = 0
    count1 = 0
 
    # Check number of 1's and 0's
    for i in range(len(s)):
        if (s[i] == '0'):
            count0 += 1
        else:
            count1 += 1
    sb = s
 
    # Store difference in number of 1's
    # and 0's
    g = count0 - count1
 
    # l store the value that how much 0's
    # or 1's we need to add in string
    l = n - len(s)
    l -= g
 
    # u store the count of
    # number of 0's we need to insert
    u = l // 2
    while (u > 0):
        sb += '0'
        u -= 1
    if (l % 2 != 0):
        sb += '0'
 
    while (len(sb) < n):
        sb += '1'
 
    # Return result
    return sb
 
# Driver Code
N = 7
S = "001"
 
# Function call
print(find_string(N, S))
 
# This code is contributed by shinjanpatra

C#

// C# code to implement the above approach
using System;
 
class GFG {
 
    // Function to build string
    string find_string(int n, string s)
    {
        // Declaring variable
        int count0 = 0, count1 = 0;
 
        // Check number of 1's and 0's
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '0') {
                count0++;
            }
            else {
                count1++;
            }
        }
        string sb = s;
 
        // Store difference in number of 1's
        // and 0's
        int g = count0 - count1;
 
        // l store the value that how much 0's
        // or 1's we need to add in string
        int l = n - s.Length;
        l -= g;
 
        // u store the count of
        // number of 0's we need to insert
        int u = l / 2;
        while (u > 0) {
            sb += '0';
            u--;
        }
        if (l % 2 != 0) {
            sb += '0';
        }
 
        while (sb.Length < n) {
            sb += '1';
        }
 
        // Retutrn result
        return sb;
    }
 
// Driver code
public static void Main()
{
        int N = 7;
        string S = "001";
        GFG g = new GFG();
 
        // Function call
        Console.Write(g.find_string(N, S));
}
}
 
// This code is contributed by sonjoy_62.

Javascript

<script>
// Javascript program for above approach
 
// Function to build string
function find_string(n, s)
{
   
    // Declaring variable
    let count0 = 0;
    let count1 = 0;
 
    // Check number of 1's and 0's
    for (let i = 0; i < s.length; i++) {
        if (s[i] == '0') {
            count0++;
        }
        else {
            count1++;
        }
    }
    let sb = s;
 
    // Store difference in number of 1's
    // and 0's
    let g = count0 - count1;
 
    // l store the value that how much 0's
    // or 1's we need to add in string
    let l = n - s.length;
    l -= g;
 
    // u store the count of
    // number of 0's we need to insert
    let u = Math.floor(l / 2);
    while (u > 0) {
        sb += '0';
        u--;
    }
    if (l % 2 != 0) {
        sb += '0';
    }
 
    while (sb.length < n) {
        sb += '1';
    }
 
    // Return result
    return sb;
}
 
// Driver Code
let N = 7;
let S = "001";
 
// Function call
document.write(find_string(N, S));
 
// This code is contributed by Samim Hossain Mondal.
</script>
Producción

0010011

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

Publicación traducida automáticamente

Artículo escrito por lakshayr32 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *