Given a binary string str of size N, the task is to calculate the bitwise XOR of all substrings of str.
Examples:
Input: str = “11”
Output: 11
Explanation: The substrings of “11” are: 1, 1, and 11.
Their XOR = 1 ⊕ 1 ⊕ 11 = 11Input: str = “110”
Output: 111
Explanation: The substrings of 110 are: 1, 1, 0, 11, 10, 110.
Their XOR = 1 ⊕ 1 ⊕ 0 ⊕ 11 ⊕ 10 ⊕ 110 = 111Input: str = “10101”
Output: 11001
Explanation: The substrings of 10101 are: 1, 10, 101, 1010, 10101, 0, 01, 010, 0101, 1, 10, 101, 0, 01, and 1.
Their XOR = 1 ⊕ 10 ⊕ 101 ⊕ 1010 ⊕ 10101 ⊕ 0 ⊕ 01 ⊕ 010 ⊕ 0101 ⊕ 1 ⊕ 10 ⊕ 101 ⊕ 0 ⊕ 01 ⊕ 1 = 11001
Approach: This problem can be solved based on the following observation:
XOR of odd number of 1s is always 1. Otherwise, the XOR is 0.
Each jth bit can be the ith bit in a substring when 0 ≤ j ≤ N-i.
So each character has contribution for the last bit (LSB) of the result.
All characters from i = 0 to N-2 has contribution for 2nd last bit and so on.
Follow the steps mentioned below to utilize the above observation to solve this problem:
- Create an array (say occurrence[]) to store the total count of 1s having contribution for ith index from LSB end in resultant XOR.
- Now iterate from the LSB end (iterator i):
- If the total number of 1s at ith index is odd then the resultant XOR will have ith bit from the LSB end as 1.
- Otherwise, the value in ith bit will be 0.
- Return the resultant XOR.
Below is the implementation of the above approach:
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Function to find the XORstring 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 Codeint main(){ int N = 5; string str = "10101"; cout << totalXOR(str, N); return 0;} |
Java
// Java program to implement the approachimport 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 approachdef 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 Codeif __name__ == '__main__': N = 5 str = "10101" print(totalXOR(str, N)) |
C#
// C# program to implement the approachusing 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> |
Output
11001
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
