Construya una string binaria siguiendo las restricciones dadas

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)

Publicación traducida automáticamente

Artículo escrito por Samdare B 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 *