Dados tres enteros A , B y X . La tarea es construir una string binaria str que tenga exactamente un número A de 0 y un número B de 1 siempre que tenga que haber al menos X índices tales que str[i] != str[i+1] . Las entradas son tales que siempre hay una solución válida.
Ejemplos:
Entrada: A = 2, B = 2, X = 1
Salida: 1100
Hay dos 0 y dos 1 y un índice (=X) tal que s[i] != s[i+1] (es decir, i = 1)
Entrada: A = 4, B = 3, X = 2
Salida: 0111000
Acercarse:
- Divide x por 2 y guárdalo en una variable d .
- Compruebe si d es par y d / 2 != a , si la condición es verdadera , imprima 0 y disminuya d y a en 1 .
- Bucle de 1 a d e imprima 10 y al final actualice a = a – d y b = b – d .
- Finalmente imprima los 0 y 1 restantes dependiendo de los valores de a y b .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Function to print a binary string which has
// 'a' number of 0's, 'b' number of 1's and there are
// at least 'x' indices such that s[i] != s[i+1]
int constructBinString(int a, int b, int x)
{
int d, i;
// Divide index value by 2 and store
// it into d
d = x / 2;
// If index value x is even and
// x/2 is not equal to a
if (x % 2 == 0 && x / 2 != a) {
d--;
cout << 0;
a--;
}
// Loop for d for each d print 10
for (i = 0; i < d; i++)
cout << "10";
// subtract d from a and b
a = a - d;
b = b - d;
// Loop for b to print remaining 1's
for (i = 0; i < b; i++) {
cout << "1";
}
// Loop for a to print remaining 0's
for (i = 0; i < a; i++) {
cout << "0";
}
}
// Driver code
int main()
{
int a = 4, b = 3, x = 2;
constructBinString(a, b, x);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to print a binary string which has
// 'a' number of 0's, 'b' number of 1's and there are
// at least 'x' indices such that s[i] != s[i+1]
static void constructBinString(int a, int b, int x)
{
int d, i;
// Divide index value by 2 and store
// it into d
d = x / 2;
// If index value x is even and
// x/2 is not equal to a
if (x % 2 == 0 && x / 2 != a)
{
d--;
System.out.print("0");
a--;
}
// Loop for d for each d print 10
for (i = 0; i < d; i++)
System.out.print("10");
// subtract d from a and b
a = a - d;
b = b - d;
// Loop for b to print remaining 1's
for (i = 0; i < b; i++)
{
System.out.print("1");
}
// Loop for a to print remaining 0's
for (i = 0; i < a; i++)
{
System.out.print("0");
}
}
// Driver code
public static void main(String[] args)
{
int a = 4, b = 3, x = 2;
constructBinString(a, b, x);
}
}
// This code is contributed
// by Mukul Singh
Python3
# Python3 implementation of the above approach
# Function to print a binary string which
# has 'a' number of 0's, 'b' number of 1's
# and there are at least 'x' indices such
# that s[i] != s[i+1]
def constructBinString(a, b, x):
# Divide index value by 2 and
# store it into d
d = x // 2
# If index value x is even and
# x/2 is not equal to a
if x % 2 == 0 and x // 2 != a:
d -= 1
print("0", end = "")
a -= 1
# Loop for d for each d print 10
for i in range(d):
print("10", end = "")
# subtract d from a and b
a = a - d
b = b - d
# Loop for b to print remaining 1's
for i in range(b):
print("1", end = "")
# Loop for a to print remaining 0's
for i in range(a):
print("0", end = "")
# Driver Code
if __name__ == "__main__":
a, b, x = 4, 3, 2
constructBinString(a, b, x)
# This code is contributed by Rituraj_Jain
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to print a binary string which has
// 'a' number of 0's, 'b' number of 1's and there are
// at least 'x' indices such that s[i] != s[i+1]
static void constructBinString(int a, int b, int x)
{
int d, i;
// Divide index value by 2 and store
// it into d
d = x / 2;
// If index value x is even and
// x/2 is not equal to a
if (x % 2 == 0 && x / 2 != a)
{
d--;
Console.Write("0");
a--;
}
// Loop for d for each d print 10
for (i = 0; i < d; i++)
Console.Write("10");
// subtract d from a and b
a = a - d;
b = b - d;
// Loop for b to print remaining 1's
for (i = 0; i < b; i++)
{
Console.Write("1");
}
// Loop for a to print remaining 0's
for (i = 0; i < a; i++)
{
Console.Write("0");
}
}
// Driver code
public static void Main()
{
int a = 4, b = 3, x = 2;
constructBinString(a, b, x);
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP implementation of the
// above approach
// Function to print a binary string
// which has 'a' number of 0's, 'b'
// number of 1's and there are at least
// 'x' indices such that s[i] != s[i+1]
function constructBinString($a, $b, $x)
{
$d; $i;
// Divide index value by 2
// and store it into d
$d = $x / 2;
// If index value x is even and
// x/2 is not equal to a
if ($x % 2 == 0 && $x / 2 != $a)
{
$d--;
echo 0;
$a--;
}
// Loop for d for each d print 10
for ($i = 0; $i < $d; $i++)
echo "10";
// subtract d from a and b
$a = $a - $d;
$b = $b - $d;
// Loop for b to print remaining 1's
for ($i = 0; $i < $b; $i++)
{
echo "1";
}
// Loop for a to print remaining 0's
for ($i = 0; $i < $a; $i++)
{
echo "0";
}
}
// Driver code
$a = 4;
$b = 3;
$x = 2;
constructBinString($a, $b, $x);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to print a binary string which has
// 'a' number of 0's, 'b' number of 1's and there are
// at least 'x' indices such that s[i] != s[i+1]
function constructBinString(a, b, x)
{
let d, i;
// Divide index value by 2 and store
// it into d
d = parseInt(x / 2, 10);
// If index value x is even and
// x/2 is not equal to a
if (x % 2 == 0 && parseInt(x / 2, 10) != a)
{
d--;
document.write("0");
a--;
}
// Loop for d for each d print 10
for (i = 0; i < d; i++)
document.write("10");
// subtract d from a and b
a = a - d;
b = b - d;
// Loop for b to print remaining 1's
for (i = 0; i < b; i++)
{
document.write("1");
}
// Loop for a to print remaining 0's
for (i = 0; i < a; i++)
{
document.write("0");
}
}
let a = 4, b = 3, x = 2;
constructBinString(a, b, x);
</script>
Producción:
0111000
Complejidad del tiempo: O(max(a,b,x))
Espacio Auxiliar: O(1)