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>
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