Comprobar si una codificación representa una string binaria única

Dada una codificación de una string binaria de longitud k, la tarea es encontrar si la codificación dada identifica de manera única una string binaria o no. La codificación tiene recuentos de 1 contiguos (separados por 0). 
Por ejemplo, la codificación de 11111 es {5}, la codificación de 01101010 es {2, 1, 1} y la codificación de 111011 es {3, 2}.

Ejemplos: 

Input: encoding[] = {3, 3, 3} 
       Length, k = 12 
Output: No

Explanation: There are more than one possible 
binary strings. The strings are 111011101110
and 011101110111. Hence “No” 

Input: encoding[] = {3, 3, 2} 
       Length, k = 10 
Output: Yes

Explanation: There is only one possible encoding 
that is 1110111011

Un enfoque ingenuo es tomar una string vacía y atravesar los n enteros hasta el número de 1 como se indica en la codificación [0] y luego agregarle 1 cero, luego codificar [1] 1 y al final verificar si la longitud de la string es igual a k luego imprima “Sí” o imprima “No” 

Un enfoque eficiente será sumar todos los n enteros para sumar, y luego sumar (n-1) para sumar y verificar si es igual a K, ya que n-1 será el número de ceros entre cada 1. Compruebe si la suma es igual a k, para obtener exactamente una string o si hay más o ninguna. 

Implementación:

// C++ program to check if given encoding
// represents a single string.
#include <bits/stdc++.h>
using namespace std;
 
bool isUnique(int a[], int n, int k)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += a[i];
     
    sum += n - 1;
     
    // Return true if sum becomes k
    return (sum == k);
}
 
// Driver Code
int main()
{
 
int a[] = {3, 3, 3};
int n = sizeof(a) / sizeof(a[0]);
int k = 12;
if (isUnique(a, n, k))
    cout << "Yes";
else
    cout << "No";
return 0;
}

// Java program to check if given encoding
// represents a single string.
import java.io.*;
 
class GFG
{
    static boolean isUnique(int []a, int n, int k)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += a[i];
         
        sum += n - 1;
         
        // Return true if sum becomes k
        return (sum == k);
    }
     
    // Driver Code
    static public void main (String[] args)
    {
        int []a = {3, 3, 3};
        int n = a.length;
        int k = 12;
        if (isUnique(a, n, k))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by vt_m

# Python 3 program to check if given
# encoding represents a single string.
 
def isUnique(a, n, k):
    sum = 0
    for i in range(0, n, 1):
        sum += a[i]
     
    sum += n - 1
     
    # Return true if sum becomes k
    return (sum == k)
 
# Driver Code
if __name__ == '__main__':
    a = [3, 3, 3]
    n = len(a)
    k = 12
    if (isUnique(a, n, k)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by
# Surndra_Gangwar

// C# program to check if given encoding
// represents a single string.
using System;
 
class GFG
{
    static bool isUnique(int []a, int n, int k)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += a[i];
         
        sum += n - 1;
         
        // Return true if sum becomes k
        return (sum == k);
    }
     
    // Driver Code
    static public void Main ()
    {
        int []a = {3, 3, 3};
        int n = a.Length;
        int k = 12;
        if (isUnique(a, n, k))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
                 
    }
}
 
// This code is contributed by vt_m

<?php
// PHP program to check
// if given encoding
// represents a single string
 
function isUnique( $a, $n, $k)
{
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum += $a[$i];
     
    $sum += $n - 1;
     
    // Return true if
    // sum becomes k
    return ($sum == $k);
}
 
// Driver Code
$a = array(3, 3, 3);
$n = count($a);
$k = 12;
if (isUnique($a, $n,$k))
    echo"Yes";
else
    echo "No";
     
// This code is contributed by anuj_67.
?>

<script>
// javascript program to check if given encoding
// represents a single string.
    function isUnique(a , n , k)
    {
        var sum = 0;
        for (i = 0; i < n; i++)
            sum += a[i];
 
        sum += n - 1;
 
        // Return true if sum becomes k
        return (sum == k);
    }
 
    // Driver Code
        var a = [ 3, 3, 3 ];
        var n = a.length;
        var k = 12;
        if (isUnique(a, n, k))
            document.write("Yes");
        else
            document.write("No");
 
// This code is contributed by Rajput-Ji
</script>

No

Complejidad temporal : O(n) 
Espacio auxiliar : O(1) 

Este artículo es una contribución de Striver . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.