Given an encoding of a binary string of length k, the task is to find if the given encoding uniquely identifies a binary string or not. The encoding has counts of contiguous 1s (separated by 0s).
For example, encoding of 11111 is {5}, encoding of 01101010 is {2, 1, 1} and encoding of 111011 is {3, 2}.
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
A naive approach is to take an empty string and traverse through the n integers to no of 1s as given in encoding[0] and then add 1 zero to it, then encoding[1] 1s, and at the end check if the string length is equal to k then print “Yes” or print “No”
C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool is_unique_encoding(vector< int > encoding, int k) {
string binary_str = "" ;
for ( int count : encoding) {
binary_str += string(count, '1' ) + "0" ;
}
binary_str = binary_str.substr(0, binary_str.length() - 1);
if (binary_str.length() != k) {
return false ;
}
return true ;
}
int main() {
vector< int > encoding = {3, 3, 3};
int k = 12;
if (is_unique_encoding(encoding, k)) {
cout << "yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
|
Java
import java.util.ArrayList;
public class Main {
public static boolean isUniqueEncoding(ArrayList<Integer> encoding, int k) {
String binaryStr = "" ;
for ( int count : encoding) {
binaryStr += "1" .repeat(count) + "0" ;
}
binaryStr = binaryStr.substring( 0 , binaryStr.length() - 1 );
if (binaryStr.length() != k) {
return false ;
}
return true ;
}
public static void main(String[] args) {
ArrayList<Integer> encoding = new ArrayList<Integer>();
encoding.add( 3 );
encoding.add( 3 );
encoding.add( 3 );
int k = 12 ;
if (isUniqueEncoding(encoding, k)) {
System.out.println( "YES" );
} else {
System.out.println( "NO" );
}
}
}
|
Python
def isUniqueEncoding(encoding, k):
binaryStr = ""
for count in encoding:
binaryStr + = "1" * count + "0"
binaryStr = binaryStr[: - 1 ]
if len (binaryStr) ! = k:
return False
return True
if __name__ = = '__main__' :
encoding = [ 3 , 3 , 3 ]
k = 12
if isUniqueEncoding(encoding, k):
print ( "YES" )
else :
print ( "NO" )
|
C#
using System;
using System.Collections.Generic;
class Program
{
static bool IsUniqueEncoding(List< int > encoding, int k)
{
string binaryStr = "" ;
foreach ( int count in encoding)
{
binaryStr += new string ( '1' , count) + "0" ;
}
binaryStr = binaryStr.Substring(0, binaryStr.Length - 1);
if (binaryStr.Length != k)
{
return false ;
}
return true ;
}
static void Main()
{
List< int > encoding = new List< int > { 3, 3, 3 };
int k = 12;
if (IsUniqueEncoding(encoding, k))
{
Console.WriteLine( "yes" );
}
else
{
Console.WriteLine( "No" );
}
}
}
|
Javascript
function isUniqueEncoding(encoding, k) {
let binaryStr = "" ;
for (let count of encoding) {
binaryStr += "1" .repeat(count) + "0" ;
}
binaryStr = binaryStr.substring(0, binaryStr.length - 1);
if (binaryStr.length !== k) {
return false ;
}
return true ;
}
let encoding = [3, 3, 3];
let k = 12;
if (isUniqueEncoding(encoding, k)) {
console.log( "YES" );
} else {
console.log( "NO" );
}
|
An efficient approach will be to add all the n integers to sum, and then add (n-1) to sum and check if it is equal to K, as n-1 will be the number of zeros in between every 1’s. Check if sum is equal to k, to get exactly one string or else there are more or none.
C++
#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 (sum == k);
}
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
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 (sum == k);
}
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" );
}
}
|
Python3
def isUnique(a, n, k):
sum = 0
for i in range ( 0 , n, 1 ):
sum + = a[i]
sum + = n - 1
return ( sum = = k)
if __name__ = = '__main__' :
a = [ 3 , 3 , 3 ]
n = len (a)
k = 12
if (isUnique(a, n, k)):
print ( "Yes" )
else :
print ( "No" )
|
C#
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 (sum == k);
}
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" );
}
}
|
Javascript
<script>
function isUnique(a , n , k)
{
var sum = 0;
for (i = 0; i < n; i++)
sum += a[i];
sum += n - 1;
return (sum == k);
}
var a = [ 3, 3, 3 ];
var n = a.length;
var k = 12;
if (isUnique(a, n, k))
document.write( "Yes" );
else
document.write( "No" );
</script>
|
PHP
<?php
function isUnique( $a , $n , $k )
{
$sum = 0;
for ( $i = 0; $i < $n ; $i ++)
$sum += $a [ $i ];
$sum += $n - 1;
return ( $sum == $k );
}
$a = array (3, 3, 3);
$n = count ( $a );
$k = 12;
if (isUnique( $a , $n , $k ))
echo "Yes" ;
else
echo "No" ;
?>
|
Time complexity : O(n)
Auxiliary Space : O(1)