Decodificar un patrón dado de dos maneras (Pregunta de entrevista de Flipkart)

Un remitente envía una string binaria a un receptor mientras cifra los dígitos. Se le proporciona una forma cifrada de string. Ahora, el receptor necesita decodificar la string, y durante la decodificación hubo 2 enfoques.

Deje que la string binaria cifrada sea P[] y la string real sea S[]. 

First, receiver starts with first character as 0; 
S[0] = 0 // First decoded bit is 1
Remaining bits or S[i]s are decoded using following formulas.
P[1] = S[1] + S[0] 
P[2] = S[2] + S[1] + S[0] 
P[3] = S[3] + S[2] + S[1] 
and so on ...

Second, Receiver starts with first character as 1; 
S[0] = 1 // First decoded bit is 1
Remaining bits or S[i]s are decoded using following formulas.
P[1] = S[1] + S[0]  
P[2] = S[2] + S[1] + S[0] 
P[3] = S[3] + S[2] + S[1] 
and so on ...

Debe imprimir dos strings generadas usando dos diferentes después de la evaluación de la primera y la segunda técnica. Si alguna string contiene otros números binarios, debe imprimir NINGUNO. 

Input1; 0123210
Output: 0111000, NONE

Explanation for first output
S[0] = 0, 
P[1] = S[1] + S[0], S[1] = 1
P[2] = S[2] + S[1] + S[0], S[2] = 1
P[3] = S[3] + S[2] + S[1], S[3] = 1
P[4] = S[4] + S[3] + S[2], S[4] = 0 
P[5] = S[5] + S[4] + S[3], S[5] = 0
P[6] = S[6] + S[5] + S[4], S[6] = 0

Explanation for second output 
S[0] = 1,
P[1] = S[1] + S[0], S[1] = 0
P[2] = s[2] + S[1] + S[0], S[2] = 1
P[3] = S[3] + S[2] + S[1], S[3] = 2, not a binary character so NONE.

Fuente: Entrevista Flipkart | Conjunto 9 (en el campus)

La idea para resolver este problema es simple, hacemos un seguimiento de los dos últimos bits decodificados. El bit actual S[i] siempre se puede calcular restando los últimos dos bits decodificados de P[i].

A continuación se muestra la implementación de la idea anterior. Almacenamos los últimos dos bits decodificados en ‘primero’ y ‘segundo’.

#include<iostream>
using namespace std;
 
// This function prints decoding of P[] with first decoded
// number as 'first'. If the decoded numbers contain anything
// other than 0, then "NONE" is printed
void decodeUtil(int P[], int n, int first)
{
    int S[n];  // array to store decoded bit pattern
    S[0] = first;  // The first number is always the given number
 
    int second = 0;  // Initialize second
 
    // Calculate all bits starting from second
    for (int i = 1; i < n; i++)
    {
        S[i] = P[i] -  first - second;
        if (S[i] != 1 && S[i] != 0)
        {
            cout << "NONE\n";
            return;
        }
        second = first;
        first = S[i];
    }
 
    // Print the output array
    for (int i = 0; i < n; i++)
       cout << S[i];
    cout << endl;
}
 
// This function decodes P[] using two techniques
// 1) Starts with 0 as first number 2) Starts 1 as first number
void decode(int P[], int n)
{
    decodeUtil(P, n, 0);
    decodeUtil(P, n, 1);
}
 
int main()
{
    int P[] = {0, 1, 2, 3, 2, 1, 0};
    int n = sizeof(P)/sizeof(P[0]);
    decode(P, n);
    return 0;
}

class GFG{
     
// This function prints decoding of P[]
// with first decoded number as 'first'.
// If the decoded numbers contain anything
// other than 0, then "NONE" is printed
public static void decodeUtil(int P[], int n,
                              int first)
{
    // Array to store decoded bit pattern
    int S[] = new int[n];
     
    // The first number is always
    // the given number
    S[0] = first; 
     
    // Initialize second
    int second = 0; 
     
    // Calculate all bits starting
    // from second
    for(int i = 1; i < n; i++)
    {
        S[i] = P[i] - first-second;
         
        if (S[i] != 1 && S[i] != 0)
        {
            System.out.println("NONE");
            return;
        }
        second = first;
        first = S[i];
    }
     
    // Print the output array
    for(int i = 0; i < n; i++)
    {
        System.out.print(S[i]);
    }
    System.out.println();
}
 
// Driver code
public static void main(String []args)
{
    int P[] = { 0, 1, 2, 3, 2, 1, 0 };
    int n = P.length;
     
    // This function decodes P[] using
    // two techniques 1) Starts with 0
    // as first number 2) Starts 1 as
    // first number
    decodeUtil(P, n, 0);
    decodeUtil(P, n, 1);
}
}
 
// This code is contributed by avanitrachhadiya2155

# This function prints decoding of P[] with
# first decoded number as 'first'. If the
# decoded numbers contain anything other
# than 0, then "NONE" is printed
def decodeUtil(P, n, first):
    S = [0 for i in range(n)]
     
    # array to store decoded bit pattern
    S[0] = first # The first number is
                 # always the given number
 
    second = 0
     
    # Initialize second
 
    # Calculate all bits starting from second
    for i in range(1, n, 1):
        S[i] = P[i] - first - second
        if (S[i] != 1 and S[i] != 0):
            print("NONE")
            return
     
        second = first
        first = S[i]
 
    # Print the output array
    for i in range(0, n, 1):
        print(S[i], end = "")
    print("\n", end = "")
 
# This function decodes P[] using
# two techniques
# 1) Starts with 0 as first number
# 2) Starts 1 as first number
def decode(P, n):
    decodeUtil(P, n, 0)
    decodeUtil(P, n, 1)
 
# Driver Code
if __name__ == '__main__':
    P = [0, 1, 2, 3, 2, 1, 0]
    n = len(P)
    decode(P, n)
     
# This code is contributed by
# Shashank_Sharma

using System;
 
class GFG{
     
// This function prints decoding of P[]
// with first decoded number as 'first'.
// If the decoded numbers contain anything
// other than 0, then "NONE" is printed
static void decodeUtil(int[] P, int n, int first)
{
     
    // Array to store decoded bit pattern
    int[] S = new int[n];
     
    // The first number is always
    // the given number
    S[0] = first;
     
    // Initialize second
    int second = 0; 
     
    // Calculate all bits starting
    // from second
    for(int i = 1; i < n; i++)
    {
        S[i] = P[i] - first - second;
         
        if (S[i] != 1 && S[i] != 0)
        {
            Console.WriteLine("NONE");
            return;
        }
        second = first;
        first = S[i];
    }
     
    // Print the output array
    for(int i = 0; i < n; i++)
    {
        Console.Write(S[i]);
    }
    Console.WriteLine();
}
 
// Driver code
static public void Main()
{
    int[] P = { 0, 1, 2, 3, 2, 1, 0 };
    int n = P.Length;
     
    // This function decodes P[] using
    // two techniques 1) Starts with 0
    // as first number 2) Starts 1 as
    // first number
    decodeUtil(P, n, 0);
    decodeUtil(P, n, 1);
}
}
 
// This code is contributed by rag2127

<?php
 
// This function prints decoding
// of P[] with first decoded
// number as 'first'. If the
// decoded numbers contain anything
// other than 0, then "NONE" is printed
function decodeUtil($P, $n, $first)
{
     
    // The first number is always
    // the given number
    $S[0] = $first;
 
    // Initialize second
    $second = 0;
 
    // Calculate all bits starting
    // from second
    for ($i = 1; $i < $n; $i++)
    {
        $S[$i] = $P[$i] - $first - $second;
        if ($S[$i] != 1 && $S[$i] != 0)
        {
            echo "NONE\n";
            return;
        }
        $second = $first;
        $first = $S[$i];
    }
 
    // Print the output array
    for ($i = 0; $i < $n; $i++)
    echo $S[$i];
    echo "\n";
}
 
// This function decodes P[]
// using two techniques
// 1) Starts with 0 as first number
// 2) Starts 1 as first number
function decode($P, $n)
{
    decodeUtil($P, $n, 0);
    decodeUtil($P, $n, 1);
}
 
    // Driver Code
    $P=array (0, 1, 2, 3, 2, 1, 0);
    $n = sizeof($P);
    decode($P, $n);
 
// This code is contributed by ajit
?>

<script>
    // This function prints decoding of P[]
    // with first decoded number as 'first'.
    // If the decoded numbers contain anything
    // other than 0, then "NONE" is printed
    function decodeUtil(P, n, first)
    {
 
        // Array to store decoded bit pattern
        let S = new Array(n);
 
        // The first number is always
        // the given number
        S[0] = first;
 
        // Initialize second
        let second = 0;
 
        // Calculate all bits starting
        // from second
        for(let i = 1; i < n; i++)
        {
            S[i] = P[i] - first - second;
 
            if (S[i] != 1 && S[i] != 0)
            {
                document.write("NONE" + "</br>");
                return;
            }
            second = first;
            first = S[i];
        }
 
        // Print the output array
        for(let i = 0; i < n; i++)
        {
            document.write(S[i]);
        }
        document.write("</br>");
    }
     
    let P = [ 0, 1, 2, 3, 2, 1, 0 ];
    let n = P.length;
      
    // This function decodes P[] using
    // two techniques 1) Starts with 0
    // as first number 2) Starts 1 as
    // first number
    decodeUtil(P, n, 0);
    decodeUtil(P, n, 1);
 
</script>

0111000
NONE

Complejidad de tiempo: O(n)