XOR de todas las substrings de una string binaria dada

Dada una string binaria str de tamaño N , la tarea es calcular el XOR bit a bit de todas las substrings de str.

Ejemplos:

Entrada: str = “11”
Salida: 11
Explicación: Las substrings de “11” son: 1, 1 y 11.
Su XOR = 1 ⊕ 1 ⊕ 11 = 11

Entrada: str = “110”
Salida: 111
Explicación: Las substrings de 110 son: 1, 1, 0, 11, 10, 110. 
Su XOR = 1 ⊕ 1 ⊕ 0 ⊕ 11 ⊕ 10 ⊕ 110 = 111

Entrada: str = “10101”
Salida: 11001
Explicación: Las substrings de 10101 son: 1, 10, 101, 1010, 10101, 0, 01, 010, 0101, 1, 10, 101, 0, 01 y 1.
Sus XOR = 1 ⊕ 10 ⊕ 101 ⊕ 1010 ⊕ 10101 ⊕ 0 ⊕ 01 ⊕ 010 ⊕ 0101 ⊕ 1 ⊕ 10 ⊕ 101 ⊕ 0 ⊕ 01 ⊕ 1 = 11001

 

Planteamiento: Este problema se puede resolver con base en la siguiente observación:

El XOR de un número impar de 1 siempre es 1. De lo contrario, el XOR es 0. 
Cada j-ésimo bit puede ser el i-ésimo bit en una substring cuando 0 ≤ j ≤ Ni .
Entonces, cada carácter tiene una contribución para el último bit (LSB) del resultado. 
Todos los caracteres de i = 0 a N-2 tienen una contribución para el segundo bit y así sucesivamente.

Siga los pasos mencionados a continuación para utilizar la observación anterior para resolver este problema:

  • Cree una array (por ejemplo, ocurrencia []) para almacenar el recuento total de 1 que tienen una contribución para el i-ésimo índice desde el extremo LSB en el XOR resultante.
  • Ahora iterar desde el extremo LSB (iterador i ):
    • Si el número total de 1 en el i-ésimo índice es impar, entonces el XOR resultante tendrá el i-ésimo bit del extremo LSB como 1 .
    • De lo contrario, el valor en el i-ésimo bit será 0.
  • Devuelve el XOR resultante.

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

C++

// C++ code to implement above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the XOR
string totalXOR(string s, int n)
{
    // Vector for storing the occurrences
    vector<int> occurrence;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1')
            occurrence.push_back(i + 1);
        else
            occurrence.push_back(0);
    }
 
    // Calculating the total occurrences
    // of nth bit
    int sums
        = accumulate(occurrence.begin(),
                     occurrence.end(), 0);
    string ans = "";
    for (int i = 0; i < n; i++) {
 
        // Checking if the total occurrences
        // are odd
        if (sums % 2 == 1)
            ans = "1" + ans;
        else
            ans = "0" + ans;
        sums -= occurrence.back();
        occurrence.pop_back();
    }
    return ans;
}
 
// Driver Code
int main()
{
    int N = 5;
    string str = "10101";
    cout << totalXOR(str, N);
    return 0;
}

Java

// Java program to implement the approach
import java.io.*;
import java.util.ArrayList;
 
public class GFG {
 
  // function to find XOR
  static String totalXOR(String s, int n)
  {
 
    // initializing occurrence list
    ArrayList<Integer> occurrence
      = new ArrayList<Integer>();
    for (int i = 0; i < n; i++) {
      if ((s.charAt(i)) == '1')
        occurrence.add(i + 1);
      else
        occurrence.add(0);
    }
 
    // calculating sum of occurrence
    int sums = 0;
    for (int i : occurrence)
      sums += i;
 
    String ans = "";
    for (int i = 0; i < n; i++) {
 
      // Checking if the total occurrences
      // are odd
      if (sums % 2 == 1)
        ans = "1" + ans;
      else
        ans = "0" + ans;
 
      // subtracting last element of occurrence from
      // sums
      sums -= occurrence.get(occurrence.size() - 1);
 
      // removing last element of occurrence
      occurrence.remove(occurrence.size() - 1);
    }
 
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 5;
    String str = "10101";
    System.out.print(totalXOR(str, N));
  }
}
 
// This code is contributed by phasing17

Python3

# Python Program to implement
# above approach
def totalXOR(string, n):
   
    # Storing the occurrences of 1s
    occurrences = [i + 1 if string[i] ==
           '1' else 0 for i in range(n)]
     
    # Calculating the occurrences for nth bit
    sums = sum(occurrences)
    ans = ''
    for i in range(n):
        ans \
            = ['0', '1'][sums % 2 == 1] + ans
        # Subtracting the occurrences of
        # (i + 1)th bit from ith bit
        sums -= occurrences[-1]
        del occurrences[-1]
    return ans
 
# Driver Code
if __name__ == '__main__':
    N = 5
    str = "10101"
    print(totalXOR(str, N))

C#

// C# program to implement the approach
using System;
using System.Collections;
 
public class GFG{
 
  // function to find XOR
  static string totalXOR(string s, int n)
  {
 
    // initializing occurrence list
    ArrayList occurrence
      = new ArrayList();
    for (int i = 0; i < n; i++) {
      if (s[i] == '1')
        occurrence.Add(i + 1);
      else
        occurrence.Add(0);
    }
 
    // calculating sum of occurrence
    int sums = 0;
    foreach (var i in occurrence)
      sums = sums + (int)i;
 
    string ans = "";
    for (int i = 0; i < n; i++) {
 
      // Checking if the total occurrences
      // are odd
      if (sums % 2 == 1)
        ans = "1" + ans;
      else
        ans = "0" + ans;
 
      // subtracting last element of occurrence from
      // sums
      sums = sums - (int)occurrence[occurrence.Count - 1];
 
      // removing last element of occurrence
      occurrence.RemoveAt(occurrence.Count - 1);
    }
 
    return ans;
  }
 
  // Driver Code
  static public void Main (){
 
    int N = 5;
    string str = "10101";
    Console.Write(totalXOR(str, N));
  }
}
 
// This code is contributed by hrithikgarg03188.

Javascript

<script>
    // JavaScript code to implement above approach
 
    // Function to find the XOR
    const totalXOR = (s, n) => {
     
        // Vector for storing the occurrences
        let occurrence = [];
        for (let i = 0; i < n; i++) {
            if (s[i] == '1')
                occurrence.push(i + 1);
            else
                occurrence.push(0);
        }
 
        // Calculating the total occurrences
        // of nth bit
        let sums = 0;
        for (let itm in occurrence) sums += occurrence[itm];
 
        let ans = "";
        for (let i = 0; i < n; i++) {
 
            // Checking if the total occurrences
            // are odd
            if (sums % 2 == 1)
                ans = "1" + ans;
            else
                ans = "0" + ans;
            sums -= occurrence[occurrence.length - 1];
            occurrence.pop();
        }
        return ans;
    }
 
    // Driver Code
    let N = 5;
    let str = "10101";
    document.write(totalXOR(str, N));
 
// This code is contributed by rakeshsahni
 
</script>
Producción

11001

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

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