Genere una string con distancia de Hamming como la mitad de la distancia de Hamming entre las strings A y B

Posted on by Rudeus Greyrat

Dadas dos strings binarias A y B de longitud N , la tarea es encontrar la string binaria cuya distancia de Hamming a las strings A y B es la mitad de la distancia de Hamming de A y B .
Ejemplos: 
 

Entrada: A = “1001010”, B = “0101010” 
Salida: 0001010 
Explicación: 
La distancia de hamming de la string A y B es 2. 
La distancia de hamming de la string de salida a A es 1. 
La distancia de hamming de la string de salida a B es 1.
Entrada: A = “1001010”, B = “1101010” 
Salida: No es posible 
Explicación: 
No existe ninguna string que satisfaga nuestra condición.
 

Enfoque ingenuo: un enfoque ingenuo es generar todas las strings binarias posibles de la longitud N y calcular la distancia de Hamming de cada string con A y B. Si la distancia de Hamming entre la string generada y la string dada A y B es la mitad de la distancia de Hamming entre A y B , entonces la string generada es la string resultante. De lo contrario, no existe tal string.
Complejidad de tiempo: O(2 N )
Enfoque eficiente: 
 

  1. Encuentre la distancia de Hamming ( digamos a ) entre las dos cuerdas A y B dadas . Si a es impar, no podemos generar otra string con Distancia de Hamming ( a /2 ) con las strings A y B.
  2. Si a es par, elija los primeros ( a/2 ) caracteres de la string A que no sean iguales a la string B y los siguientes ( a/2 ) caracteres de la string B que no sean iguales a la string A para crear la string resultante.
  3. Agregue los caracteres iguales de la string A y B a la string resultante.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the above
// approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required
// string
void findString(string A, string B)
{
    int dist = 0;
 
    // Find the hamming distance
    // between A and B
    for (int i = 0; A[i]; i++) {
        if (A[i] != B[i]) {
            dist++;
        }
    }
 
    // If distance is odd, then
    // resultant string is not
    // possible
    if (dist & 1) {
        cout << "Not Possible"
             << endl;
    }
 
    // Make the resultant string
    else {
 
        // To store the final
        // string
        string res = "";
 
        int K = dist / 2;
        // Pick k characters from
        // each string
 
        for (int i = 0; A[i]; i++) {
 
            // Pick K characters
            // from string B
            if (A[i] != B[i] && K > 0) {
                res.push_back(B[i]);
                K--;
            }
 
            // Pick K characters
            // from string A
            else if (A[i] != B[i]) {
                res.push_back(A[i]);
            }
 
            // Append the res characters
            // from string to the
            // resultant string
            else {
                res.push_back(A[i]);
            }
        }
 
        // Print the resultant
        // string
        cout << res << endl;
    }
}
 
// Driver's Code
int main()
{
    string A = "1001010";
    string B = "0101010";
 
    // Function to find the resultant
    // string
    findString(A, B);
    return 0;
}

Java

// Java implementation of the above
// approach
class GFG
{
 
    // Function to find the required
    // string
    static void findString(String A, String B)
    {
        int dist = 0;
     
        // Find the hamming distance
        // between A and B
        for (int i = 0; i < A.length(); i++)
        {
            if(A.charAt(i) != B.charAt(i))
                dist++;
        }
     
        // If distance is odd, then
        // resultant string is not
        // possible
        if((dist & 1) == 1)
        {
            System.out.println("Not Possible");
        }
     
        // Make the resultant string
        else
        {
     
            // To store the final
            // string
            String res = "";
     
            int K = (int)dist / 2;
             
            // Pick k characters from
            // each string
            for (int i = 0; i < A.length(); i++) {
     
                // Pick K characters
                // from string B
                if (A.charAt(i) != B.charAt(i) && K > 0) {
                    res += B.charAt(i);
                    K--;
                }
     
                // Pick K characters
                // from string A
                else if (A.charAt(i) != B.charAt(i)) {
                    res += A.charAt(i);
                }
     
                // Append the res characters
                // from string to the
                // resultant string
                else {
                    res += A.charAt(i);
                }
            }
     
            // Print the resultant
            // string
            System.out.println(res) ;
        }
    }
     
    // Driver's Code
    public static void main (String[] args)
    {
        String A = "1001010";
        String B = "0101010";
     
        // Function to find the resultant
        // string
        findString(A, B);
    }
}
 
// This code is contributed by Yash_R

Python3

# Python3 implementation of the above
# approach
 
# Function to find the required
# string
def findString(A, B) :
 
    dist = 0;
 
    # Find the hamming distance
    # between A and B
    for i in range(len(A)) :
        if (A[i] != B[i]) :
            dist += 1;
 
    # If distance is odd, then
    # resultant string is not
    # possible
    if (dist & 1) :
        print("Not Possible");
 
    # Make the resultant string
    else :
 
        # To store the final
        # string
        res = "";
 
        K = dist // 2;
         
        # Pick k characters from
        # each string
 
        for i in range(len(A)) :
 
            # Pick K characters
            # from string B
            if (A[i] != B[i] and K > 0) :
                res += B[i];
                K -= 1;
 
            # Pick K characters
            # from string A
            elif (A[i] != B[i]) :
                res += A[i];
         
            # Append the res characters
            # from string to the
            # resultant string
            else :
                res += A[i];
 
        # Print the resultant
        # string
        print(res);
 
# Driver's Code
if __name__ == "__main__" :
 
    A = "1001010";
    B = "0101010";
 
    # Function to find the resultant
    # string
    findString(A, B);
     
# This code is contributed by Yash_R

C#

// C# implementation of the above approach
using System;
 
class GFG
{
 
    // Function to find the required
    // string
    static void findString(string A, string B)
    {
        int dist = 0;
     
        // Find the hamming distance
        // between A and B
        for (int i = 0; i < A.Length; i++)
        {
            if(A[i] != B[i])
                dist++;
        }
     
        // If distance is odd, then
        // resultant string is not
        // possible
        if((dist & 1) == 1)
        {
            Console.WriteLine("Not Possible");
        }
     
        // Make the resultant string
        else
        {
     
            // To store the final
            // string
            string res = "";
     
            int K = (int)dist / 2;
             
            // Pick k characters from
            // each string
            for (int i = 0; i < A.Length; i++) {
     
                // Pick K characters
                // from string B
                if (A[i] != B[i] && K > 0) {
                    res += B[i];
                    K--;
                }
     
                // Pick K characters
                // from string A
                else if (A[i] != B[i]) {
                    res += A[i];
                }
     
                // Append the res characters
                // from string to the
                // resultant string
                else {
                    res += A[i];
                }
            }
     
            // Print the resultant
            // string
            Console.WriteLine(res) ;
        }
    }
     
    // Driver's Code
    public static void Main (string[] args)
    {
        string A = "1001010";
        string B = "0101010";
     
        // Function to find the resultant
        // string
        findString(A, B);
    }
}
 
// This code is contributed by Yash_R

Javascript

<script>
 
// JavaScript implementation of the above
// approach
 
 
// Function to find the required
// string
function findString(A, B)
{
    let dist = 0;
 
    // Find the hamming distance
    // between A and B
    for (let i = 0; A[i]; i++) {
        if (A[i] != B[i]) {
            dist++;
        }
    }
 
    // If distance is odd, then
    // resultant string is not
    // possible
    if (dist & 1) {
        document.write("Not Possible","</br>");
    }
 
    // Make the resultant string
    else {
 
        // To store the final
        // string
        let res = "";
 
        let K = Math.floor(dist / 2);
        // Pick k characters from
        // each string
 
        for (let i = 0; A[i]; i++) {
 
            // Pick K characters
            // from string B
            if (A[i] != B[i] && K > 0) {
                res+=(B[i]);
                K--;
            }
 
            // Pick K characters
            // from string A
            else if (A[i] != B[i]) {
                res+=(A[i]);
            }
 
            // Append the res characters
            // from string to the
            // resultant string
            else {
                res+=(A[i]);
            }
        }
 
        // Print the resultant
        // string
        document.write(res,"</br>");
    }
}
 
// Driver's Code
let A = "1001010";
let B = "0101010";
 
// Function to find the resultant
// string
findString(A, B);
     
// This code is contributed by shinjanpatra
 
</script>
Producción: 

0001010

 

Complejidad de tiempo: O(N), donde N es la longitud de la string.

Espacio Auxiliar: O(N)
 

Publicación traducida automáticamente

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