Dados dos números enteros N y M , la tarea es construir una string binaria con las siguientes condiciones:
- La string binaria consta de N 0 y M 1
- La string binaria tiene como máximo K 1 consecutivos.
- La string binaria no contiene ningún 0 adyacente.
Si no es posible construir una string binaria de este tipo, imprima -1 .
Ejemplos:
Entrada: N = 5, M = 9, K = 2
Salida: 01101101101101
Explicación:
La string “01101101101101” cumple las siguientes condiciones:
- No hay 0 consecutivos presentes.
- No hay más de K(= 2) 1 consecutivos presentes.
Entrada: N = 4, M = 18, K = 4
Salida: 1101111011110111101111
Acercarse:
Para construir una string binaria que satisfaga las propiedades dadas, observe lo siguiente:
- Para que no haya dos ‘ 0 ‘ consecutivos , debe haber al menos un ‘ 1 ‘ entre ellos.
- Por lo tanto, para un número N de ‘ 0 ‘, debe haber al menos N-1 ‘ 1 ‘ presentes para que se genere una string del tipo requerido.
- Dado que no se pueden colocar juntos más de K ‘ 1 ‘ consecutivos , para N 0 , puede haber un máximo de (N+1) * K ‘1 ‘ posibles.
- Por lo tanto, el número de ‘ 1 ‘ debe estar dentro del rango:
n-1? ¿M? (N + 1) * K
- Si los valores dados N y M no satisfacen la condición anterior, imprima -1 .
- De lo contrario, siga los pasos a continuación para resolver el problema:
- Agregue ‘ 0 ‘ a la string final.
- Inserte ‘ 1 ‘ entre cada par de ‘ 0′ s. Reste N – 1 de M , ya que ya se han colocado N – 1 ‘ 1 ‘s.
- Para los ‘ 1 ‘ restantes , coloque min(K – 1, M) ‘ 1 ‘ junto a cada ‘ 1 ‘ ya colocado, para asegurarse de que no se coloquen más de K ‘1 juntos.
- Para los ‘ 1 ‘ restantes , agréguelos al principio y al final de la string final.
- Finalmente, imprima la string generada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to construct the binary string
string ConstructBinaryString(int N, int M,
int K)
{
// Conditions when string construction
// is not possible
if (M < (N - 1) || M > K * (N + 1))
return "-1";
string ans = "";
// Stores maximum 1's that
// can be placed in between
int l = min(K, M / (N - 1));
int temp = N;
while (temp--) {
// Place 0's
ans += '0';
if (temp == 0)
break;
// Place 1's in between
for (int i = 0; i < l; i++) {
ans += '1';
}
}
// Count remaining M's
M -= (N - 1) * l;
if (M == 0)
return ans;
l = min(M, K);
// Place 1's at the end
for (int i = 0; i < l; i++)
ans += '1';
M -= l;
// Place 1's at the beginning
while (M > 0) {
ans = '1' + ans;
M--;
}
// Return the final string
return ans;
}
// Driver Code
int main()
{
int N = 5, M = 9, K = 2;
cout << ConstructBinaryString(N, M, K);
}
Java
// Java implementation of
// the above approach
class GFG{
// Function to construct the binary string
static String ConstructBinaryString(int N, int M,
int K)
{
// Conditions when string construction
// is not possible
if (M < (N - 1) || M > K * (N + 1))
return "-1";
String ans = "";
// Stores maximum 1's that
// can be placed in between
int l = Math.min(K, M / (N - 1));
int temp = N;
while (temp != 0)
{
temp--;
// Place 0's
ans += '0';
if (temp == 0)
break;
// Place 1's in between
for(int i = 0; i < l; i++)
{
ans += '1';
}
}
// Count remaining M's
M -= (N - 1) * l;
if (M == 0)
return ans;
l = Math.min(M, K);
// Place 1's at the end
for(int i = 0; i < l; i++)
ans += '1';
M -= l;
// Place 1's at the beginning
while (M > 0)
{
ans = '1' + ans;
M--;
}
// Return the final string
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 5, M = 9, K = 2;
System.out.println(ConstructBinaryString(N, M, K));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 implementation of # the above approach # Function to construct the binary string def ConstructBinaryString(N, M, K): # Conditions when string construction # is not possible if(M < (N - 1) or M > K * (N + 1)): return '-1' ans = "" # Stores maximum 1's that # can be placed in between l = min(K, M // (N - 1)) temp = N while(temp): temp -= 1 # Place 0's ans += '0' if(temp == 0): break # Place 1's in between for i in range(l): ans += '1' # Count remaining M's M -= (N - 1) * l if(M == 0): return ans l = min(M, K) # Place 1's at the end for i in range(l): ans += '1' M -= l # Place 1's at the beginning while(M > 0): ans = '1' + ans M -= 1 # Return the final string return ans # Driver Code if __name__ == '__main__': N = 5 M = 9 K = 2 print(ConstructBinaryString(N, M , K)) # This code is contributed by Shivam Singh
C#
// C# implementation of
// the above approach
using System;
class GFG{
// Function to construct the binary string
static String ConstructBinaryString(int N, int M,
int K)
{
// Conditions when string construction
// is not possible
if (M < (N - 1) || M > K * (N + 1))
return "-1";
string ans = "";
// Stores maximum 1's that
// can be placed in between
int l = Math.Min(K, M / (N - 1));
int temp = N;
while (temp != 0)
{
temp--;
// Place 0's
ans += '0';
if (temp == 0)
break;
// Place 1's in between
for(int i = 0; i < l; i++)
{
ans += '1';
}
}
// Count remaining M's
M -= (N - 1) * l;
if (M == 0)
return ans;
l = Math.Min(M, K);
// Place 1's at the end
for(int i = 0; i < l; i++)
ans += '1';
M -= l;
// Place 1's at the beginning
while (M > 0)
{
ans = '1' + ans;
M--;
}
// Return the final string
return ans;
}
// Driver code
public static void Main(string[] args)
{
int N = 5, M = 9, K = 2;
Console.Write(ConstructBinaryString(N, M, K));
}
}
// This code is contributed by Ritik Bansal
Javascript
<script>
// JavaScript program for the above approach
// Function to construct the binary string
function ConstructBinaryString(N, M, K)
{
// Conditions when string construction
// is not possible
if (M < (N - 1) || M > K * (N + 1))
return "-1";
let ans = "";
// Stores maximum 1's that
// can be placed in between
let l = Math.min(K, M / (N - 1));
let temp = N;
while (temp != 0)
{
temp--;
// Place 0's
ans += '0';
if (temp == 0)
break;
// Place 1's in between
for(let i = 0; i < l; i++)
{
ans += '1';
}
}
// Count remaining M's
M -= (N - 1) * l;
if (M == 0)
return ans;
l = Math.min(M, K);
// Place 1's at the end
for(let i = 0; i < l; i++)
ans += '1';
M -= l;
// Place 1's at the beginning
while (M > 0)
{
ans = '1' + ans;
M--;
}
// Return the final string
return ans;
}
// Driver Code
let N = 5, M = 9, K = 2;
document.write(ConstructBinaryString(N, M, K));
</script>
Producción:
01101101101101
Complejidad temporal: O(N+M)
Espacio auxiliar: O(N+M)