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 = 11Entrada: 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 = 111Entrada: 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>
11001
Complejidad temporal: O(N)
Espacio auxiliar: O(N)