Comprobar si se puede formar una string binaria concatenando números N dados secuencialmente

Dada una secuencia de ‘n’ números (sin ceros a la izquierda), la tarea es encontrar si es posible crear una string binaria concatenando estos números secuencialmente. 
Si es posible, imprima la string binaria formada; de lo contrario, imprima «-1».
Ejemplos: 
 

Entrada: arr[] = {10, 11, 1, 0, 10} 
Salida: 10111010 
Todos los números contienen los dígitos ‘1’ y ‘0’ solamente. Entonces, es posible formar una string binaria concatenando 
estos números secuencialmente, que es 10111010.
Entrada: arr[] = {1, 2, 11, 10} 
Salida: -1 
Uno de los números contiene el dígito ‘2’ que no se puede una parte de cualquier string binaria. 
Entonces, la salida es -1.

Enfoque: La observación principal es que solo podemos concatenar aquellos números que contienen los dígitos ‘1’ y ‘0’ solamente. De lo contrario, es imposible formar una string binaria.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns false if
// the number passed as argument contains
// digit(s) other than '0' or '1'
bool isBinary(int n)
{
    while (n != 0) {
        int temp = n % 10;
        if (temp != 0 && temp != 1) {
            return false;
        }
        n = n / 10;
    }
    return true;
}
 
//Function that checks whether the
//binary string can be formed or not
void formBinaryStr(int n, int a[])
{
    bool flag = true;
 
    // Empty string for storing
    // the binary number
    string s = "";
 
    for (int i = 0; i < n; i++) {
 
        // check if a[i] can be a
        // part of the binary string
        if (isBinary(a[i]))
 
            // Conversion of int into string
            s += to_string(a[i]);
        else {
 
            // if a[i] can't be a part
            // then break the loop
            flag = false;
            break;
        }
    }
 
    // possible to create binary string
    if (flag)
        cout << s << "\n";
 
    // impossible to create binary string
    else
        cout << "-1\n";
}
 
// Driver code
int main()
{
 
    int a[] = { 10, 1, 0, 11, 10 };
    int N = sizeof(a) / sizeof(a[0]);
 
    formBinaryStr(N, a);
 
    return 0;
}

Java

// Java  implementation of the approach
import java.util.*;
class Solution
{
// Function that returns false if
// the number passed as argument contains
// digit(s) other than '0' or '1'
static boolean isBinary(int n)
{
    while (n != 0) {
        int temp = n % 10;
        if (temp != 0 && temp != 1) {
            return false;
        }
        n = n / 10;
    }
    return true;
}
 
//Function that checks whether the
//binary String can be formed or not
static void formBinaryStr(int n, int a[])
{
    boolean flag = true;
 
    // Empty String for storing
    // the binary number
    String s = "";
 
    for (int i = 0; i < n; i++) {
 
        // check if a[i] can be a
        // part of the binary String
        if (isBinary(a[i]))
 
            // Conversion of int into String
            s += ""+a[i];
        else {
 
            // if a[i] can't be a part
            // then break the loop
            flag = false;
            break;
        }
    }
 
    // possible to create binary String
    if (flag)
        System.out.print( s + "\n");
 
    // impossible to create binary String
    else
        System.out.print( "-1\n");
}
 
// Driver code
public static void main(String args[])
{
 
    int a[] = { 10, 1, 0, 11, 10 };
    int N = a.length;
 
    formBinaryStr(N, a);
}
}
//contributed by Arnab Kundu

Python3

# Python3 implementation of the approach
 
# Function that returns false if the
# number passed as argument contains
# digit(s) other than '0' or '1'
def isBinary(n):
 
    while n != 0:
        temp = n % 10
        if temp != 0 and temp != 1:
            return False
         
        n = n // 10
     
    return True
 
# Function that checks whether the
# binary string can be formed or not
def formBinaryStr(n, a):
 
    flag = True
 
    # Empty string for storing
    # the binary number
    s = ""
    for i in range(0, n):
 
        # check if a[i] can be a
        # part of the binary string
        if isBinary(a[i]) == True:
             
            # Conversion of int into string
            s += str(a[i])
         
        else:
            # if a[i] can't be a part
            # then break the loop
            flag = False
            break
 
    # possible to create binary string
    if flag == True:
        print(s)
 
    # impossible to create binary string
    else:
        cout << "-1\n"
 
# Driver code
if __name__ == "__main__":
 
    a = [10, 1, 0, 11, 10]
    N = len(a)
 
    formBinaryStr(N, a)
 
# This code is contributed by Rituraj Jain

C#

// C#  implementation of the approach
using System;
 
public class Solution
{
// Function that returns false if
// the number passed as argument contains
// digit(s) other than '0' or '1'
public static bool isBinary(int n)
{
    while (n != 0)
    {
        int temp = n % 10;
        if (temp != 0 && temp != 1)
        {
            return false;
        }
        n = n / 10;
    }
    return true;
}
 
//Function that checks whether the 
//binary String can be formed or not
public static void formBinaryStr(int n, int[] a)
{
    bool flag = true;
 
    // Empty String for storing
    // the binary number
    string s = "";
 
    for (int i = 0; i < n; i++)
    {
 
        // check if a[i] can be a
        // part of the binary String
        if (isBinary(a[i]))
        {
 
            // Conversion of int into String
            s += "" + a[i];
        }
        else
        {
 
            // if a[i] can't be a part
            // then break the loop
            flag = false;
            break;
        }
    }
 
    // possible to create binary String
    if (flag)
    {
        Console.Write(s + "\n");
    }
 
    // impossible to create binary String
    else
    {
        Console.Write("-1\n");
    }
}
 
// Driver code
public static void Main(string[] args)
{
 
    int[] a = new int[] {10, 1, 0, 11, 10};
    int N = a.Length;
 
    formBinaryStr(N, a);
}
}
 
// This code is contributed by Shrikant13

PHP

<?php
// PHP implementation of the approach
 
// Function that returns false if the
// number passed as argument contains
// digit(s) other than '0' or '1'
function isBinary($n)
{
    while ($n != 0)
    {
        $temp = $n % 10;
        if ($temp != 0 && $temp != 1)
        {
            return false;
        }
        $n = intval($n / 10);
    }
    return true;
}
 
// Function that checks whether the
// binary string can be formed or not
function formBinaryStr($n, &$a)
{
    $flag = true;
 
    // Empty string for storing
    // the binary number
    $s = "";
 
    for ($i = 0; $i < $n; $i++)
    {
 
        // check if a[i] can be a
        // part of the binary string
        if (isBinary($a[$i]))
 
            // Conversion of int into string
            $s = $s.strval($a[$i]);
        else
        {
 
            // if a[i] can't be a part
            // then break the loop
            $flag = false;
            break;
        }
    }
 
    // possible to create binary string
    if ($flag)
        echo $s . "\n";
 
    // impossible to create binary string
    else
        echo "-1\n";
}
 
// Driver code
$a = array( 10, 1, 0, 11, 10 );
$N = sizeof($a) / sizeof($a[0]);
 
formBinaryStr($N, $a);
 
// This code is contributed by ita_c
?>

Javascript

<script>
 
// Javascript  implementation of the approach
 
    // Function that returns false if
    // the number passed as argument contains
    // digit(s) other than '0' or '1'
    function isBinary(n)
    {
        while (n != 0) {
            var temp = n % 10;
            if (temp != 0 && temp != 1) {
                return false;
            }
            n = parseInt(n / 10);
        }
        return true;
    }
 
    // Function that checks whether the
    // binary String can be formed or not
    function formBinaryStr(n , a) {
        var flag = true;
 
        // Empty String for storing
        // the binary number
        var s = "";
 
        for (i = 0; i < n; i++) {
 
            // check if a[i] can be a
            // part of the binary String
            if (isBinary(a[i]))
 
                // Conversion of var into String
                s += "" + a[i];
            else {
 
                // if a[i] can't be a part
                // then break the loop
                flag = false;
                break;
            }
        }
 
        // possible to create binary String
        if (flag)
            document.write(s + "\n");
 
        // impossible to create binary String
        else
            document.write("-1\n");
    }
 
    // Driver code
     
 
        var a = [ 10, 1, 0, 11, 10 ];
        var N = a.length;
 
        formBinaryStr(N, a);
 
// This code contributed by Rajput-Ji
 
</script>
Producción: 

10101110

 

Complejidad de tiempo: O(N*log(MAX)), donde N es la longitud de la array y MAX es el número máximo en la array

Espacio auxiliar: O(M), donde M es la longitud de la string

Publicación traducida automáticamente

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