Given an array arr[] of length N, the task for every array element is to print the sum of its Bitwise XOR with all other array elements.
Examples:
Input: arr[] = {1, 2, 3}
Output: 5 4 3
Explanation:
For arr[0]: arr[0] ^ arr[0] + arr[0] ^ arr[1] + arr[0] ^ arr[2] = 1^1 + 1^2 + 1^3 = 0 + 3 + 2 = 5
For arr[1]: arr[1] ^ arr[0] + arr[1] ^ arr[1] + arr[1] ^ arr[2] = 2^1 + 2^2 + 2^3 = 3 + 0 + 1 = 4
For arr[2]: arr[2] ^ arr[0] + arr[2] ^ arr[1] + arr[2] ^ arr[2] = 3^1 + 3^2 + 3^3 = 2 + 2 + 0 = 3Input : arr[] = {2, 4, 8}
Output: 16 18 22
Explanation:
For arr[0]: arr[0] ^ arr[0] + arr[0] ^ arr[1] + arr[0] ^ arr[2] = 2^2 + 2^4 + 2^8 = 0 + 6 + 10 = 16.
For arr[1]: arr[1] ^ arr[0] + arr[1] ^ arr[1] + arr[1] ^ arr[2] = 4^2 + 4^4 + 4^8 = 6 + 0 + 12 = 18
For arr[2]: arr[2] ^ arr[0] + arr[2] ^ arr[1] + arr[2] ^ arr[2] = 8^2 + 8^4 + 8^8 = 10 + 12 + 0 = 22
Naive Approach: The idea is to traverse the array and for each array element, traverse the array and calculate sum of its Bitwise XOR with all other array elements.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: To` optimize the above approach, the idea is to use property of Bitwise XOR that similar bits on xor, gives 0, or 1 otherwise. Follow the below steps to solve the problem:
- Calculate the frequency of set bits at position i where 0 <= i <= 32, across all the elements of the array in a frequency array.
- For every element X, of the array, calculate the xor sum by running a loop from i=0 to 32 and check if ith bit of X is set.
- If yes, then add (N – frequency[i])*2i to the xor sum because the set bit of X at this position will make all the set bits to zero and all the unset bits to 1.
- Otherwise, add frequency[i] * 2i to the xor sum.
- Calculate the sum of all the xor sum of every element of the array and return as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate for each array// element, sum of its Bitwise XOR with// all other array elementsvoid XOR_for_every_i(int A[], int N){ // Declare an array of size 64 // to store count of each bit int frequency_of_bits[32]{}; // Traversing the array for (int i = 0; i < N; i++) { int bit_position = 0; int M = A[i]; while (M) { // Check if bit is present of not if (M & 1) { frequency_of_bits[bit_position] += 1; } // Increase the bit position bit_position += 1; // Reduce the number to half M >>= 1; } } // Traverse the array for (int i = 0; i < N; i++) { int M = A[i]; // Stores the bit position int value_at_that_bit = 1; // Stores the sum of Bitwise XOR int XOR_sum = 0; for (int bit_position = 0; bit_position < 32; bit_position++) { // Check if bit is present of not if (M & 1) { XOR_sum += (N - frequency_of_bits[bit_position]) * value_at_that_bit; } else { XOR_sum += (frequency_of_bits[bit_position]) * value_at_that_bit; } // Reduce the number to its half M >>= 1; value_at_that_bit <<= 1; } // Print the sum for A[i] cout << XOR_sum << ' '; } return;}// Driver Codeint main(){ // Given array int A[] = { 1, 2, 3 }; // Given N int N = sizeof(A) / sizeof(A[0]); // Function Call XOR_for_every_i(A, N); return 0;} |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to calculate for each array// element, sum of its Bitwise XOR with// all other array elementsstatic void XOR_for_every_i(int A[], int N){ // Declare an array of size 64 // to store count of each bit int frequency_of_bits[] = new int[32]; // Traversing the array for(int i = 0; i < N; i++) { int bit_position = 0; int M = A[i]; while (M != 0) { // Check if bit is present of not if ((M & 1) != 0) { frequency_of_bits[bit_position] += 1; } // Increase the bit position bit_position += 1; // Reduce the number to half M >>= 1; } } // Traverse the array for(int i = 0; i < N; i++) { int M = A[i]; // Stores the bit position int value_at_that_bit = 1; // Stores the sum of Bitwise XOR int XOR_sum = 0; for(int bit_position = 0; bit_position < 32; bit_position++) { // Check if bit is present of not if ((M & 1) != 0) { XOR_sum += (N - frequency_of_bits[bit_position]) * value_at_that_bit; } else { XOR_sum += (frequency_of_bits[bit_position]) * value_at_that_bit; } // Reduce the number to its half M >>= 1; value_at_that_bit <<= 1; } // Print the sum for A[i] System.out.print( XOR_sum + " "); } return;} // Driver codepublic static void main(String[] args){ // Given array int A[] = { 1, 2, 3 }; // Given N int N = A.length; // Function Call XOR_for_every_i(A, N);}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program for the above approach # Function to calculate for each array# element, sum of its Bitwise XOR with# all other array elementsdef XOR_for_every_i(A, N): # Declare an array of size 64 # to store count of each bit frequency_of_bits = [0] * 32 # Traversing the array for i in range(N): bit_position = 0 M = A[i] while (M): # Check if bit is present of not if (M & 1 != 0): frequency_of_bits[bit_position] += 1 # Increase the bit position bit_position += 1 # Reduce the number to half M >>= 1 # Traverse the array for i in range(N): M = A[i] # Stores the bit position value_at_that_bit = 1 # Stores the sum of Bitwise XOR XOR_sum = 0 for bit_position in range(32): # Check if bit is present of not if (M & 1 != 0): XOR_sum += ((N - frequency_of_bits[bit_position]) * value_at_that_bit) else: XOR_sum += ((frequency_of_bits[bit_position]) * value_at_that_bit) # Reduce the number to its half M >>= 1 value_at_that_bit <<= 1 # Print the sum for A[i] print(XOR_sum, end = " ") return# Driver Code# Given arr1[]A = [ 1, 2, 3 ]# Size of NN = len(A) # Function CallXOR_for_every_i(A, N)# This code is contributed by code_hunt |
C#
// C# program for the above approach using System;class GFG{ // Function to calculate for each array// element, sum of its Bitwise XOR with// all other array elementsstatic void XOR_for_every_i(int[] A, int N){ // Declare an array of size 64 // to store count of each bit int[] frequency_of_bits = new int[32]; // Traversing the array for(int i = 0; i < N; i++) { int bit_position = 0; int M = A[i]; while (M != 0) { // Check if bit is present of not if ((M & 1) != 0) { frequency_of_bits[bit_position] += 1; } // Increase the bit position bit_position += 1; // Reduce the number to half M >>= 1; } } // Traverse the array for(int i = 0; i < N; i++) { int M = A[i]; // Stores the bit position int value_at_that_bit = 1; // Stores the sum of Bitwise XOR int XOR_sum = 0; for(int bit_position = 0; bit_position < 32; bit_position++) { // Check if bit is present of not if ((M & 1) != 0) { XOR_sum += (N - frequency_of_bits[bit_position]) * value_at_that_bit; } else { XOR_sum += (frequency_of_bits[bit_position]) * value_at_that_bit; } // Reduce the number to its half M >>= 1; value_at_that_bit <<= 1; } // Print the sum for A[i] Console.Write( XOR_sum + " "); } return;} // Driver Codepublic static void Main(){ // Given array int[] A = { 1, 2, 3 }; // Given N int N = A.Length; // Function Call XOR_for_every_i(A, N);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript program for the above approach // Function to calculate for each array// element, sum of its Bitwise XOR with// all other array elementsfunction XOR_for_every_i(A, N){ // Declare an array of size 64 // to store count of each bit let frequency_of_bits = new Uint8Array(32); // Traversing the array for(let i = 0; i < N; i++) { let bit_position = 0; let M = A[i]; while (M != 0) { // Check if bit is present of not if ((M & 1) != 0) { frequency_of_bits[bit_position] += 1; } // Increase the bit position bit_position += 1; // Reduce the number to half M >>= 1; } } // Traverse the array for(let i = 0; i < N; i++) { let M = A[i]; // Stores the bit position let value_at_that_bit = 1; // Stores the sum of Bitwise XOR let XOR_sum = 0; for(let bit_position = 0; bit_position < 32; bit_position++) { // Check if bit is present of not if ((M & 1) != 0) { XOR_sum += (N - frequency_of_bits[bit_position]) * value_at_that_bit; } else { XOR_sum += (frequency_of_bits[bit_position]) * value_at_that_bit; } // Reduce the number to its half M >>= 1; value_at_that_bit <<= 1; } // Print the sum for A[i] document.write( XOR_sum + " "); } return;}// Driver code // Given array let A = [ 1, 2, 3 ]; // Given N let N = A.length; // Function Call XOR_for_every_i(A, N);// This code is contributed by Surbhi Tyagi.</script> |
Output:
5 4 3
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!
