Sum of array elements after every element x is XORed itself x times
Given an array of integers, the task is to compute sum of all array elements after doing XOR of each element x with itself x times. For example, if element is 4 so we do XOR of this number with itself 4 time Like:= 4^4^4^4
Examples:
Input : arr[] = { 1, 2, 3, 5 } Output : 9 explanation: 1 + 2^2 + 3^3^3 + 5^5^5^5^5 : 9 Input : arr[] ={ 5, 6, 7, 9 } Output : 21
A Simple solution is to pick each array element one by one and do its XOR with itself according to the its value. Finally add XOR values to the result.
Below is the implementation of above idea.
C++
// C++ program to compute sum of all element after // doing Xor with itself ( element_time) #include <bits/stdc++.h> using namespace std; // function return sum of all XOR element of array int XorSum( int arr[], int n) { // store result int result = 0; // Traverse array element and apply XOR // operation on it for ( int i = 0; i < n; i++) { // XOR of current element with itself // according to value. int k = 0; for ( int j = 1; j <= arr[i]; j++) k ^= arr[i]; result += k; } return result; } // Driver program int main() { int arr[] = { 1, 2, 6, 3, 4, 5 }; int n = sizeof (arr) / sizeof (arr[0]); cout << XorSum(arr, n) << endl; return 0; } |
Java
// Java program to compute sum of all // element after doing Xor with itself // ( element_time) import java.io.*; class GFG { // function return sum of all XOR // element of array static int XorSum( int arr[], int n) { // store result int result = 0 ; // Traverse array element and apply // XOR operation on it for ( int i = 0 ; i < n; i++) { // XOR of current element with // itself according to value. int k = 0 ; for ( int j = 1 ; j <= arr[i]; j++) k ^= arr[i]; result += k; } return result; } // Driver program public static void main(String args[]) { int arr[] = { 1 , 2 , 6 , 3 , 4 , 5 }; int n = arr.length; System.out.println(XorSum(arr, n)); } } /*This code is contributed by Nikita Tiwari.*/ |
Python
# Python 3 program to compute sum of # all element after doing Xor with # itself ( element_time) # function return sum of all XOR # element of array def XorSum(arr, n) : # store result result = 0 # Traverse array element and # apply XOR operation on it for i in range ( 0 , n) : # XOR of current element # with itself according to # value. k = 0 for j in range ( 1 , arr[i] + 1 ) : k = k ^ arr[i] result = result + k return result # Driver program arr = [ 1 , 2 , 6 , 3 , 4 , 5 ] n = len (arr) print (XorSum(arr, n)) # This code is contributed by Nikita Tiwari. |
C#
// C# program to compute sum of all // element after doing Xor with itself // ( element_time) using System; class GFG { // function return sum of all XOR // element of array static int XorSum( int []arr, int n) { // store result int result = 0; // Traverse array element and apply // XOR operation on it for ( int i = 0; i < n; i++) { // XOR of current element with // itself according to value. int k = 0; for ( int j = 1; j <= arr[i]; j++) k ^= arr[i]; result += k; } return result; } // Driver program public static void Main() { int []arr = { 1, 2, 6, 3, 4, 5 }; int n = arr.Length; Console.WriteLine(XorSum(arr, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to compute // sum of all element after // doing Xor with itself // ( element_time) // function return sum of all // XOR element of array function XorSum( $arr , $n ) { // store result $result = 0; // Traverse array element // and apply XOR // operation on it for ( $i = 0; $i < $n ; $i ++) { // XOR of current element // with itself according // to value. $k = 0; for ( $j = 1; $j <= $arr [ $i ]; $j ++) $k ^= $arr [ $i ]; $result += $k ; } return $result ; } // Driver Code $arr = array (1, 2, 6, 3, 4, 5); $n = count ( $arr ); echo XorSum( $arr , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to compute sum of all element after // doing Xor with itself ( element_time) // function return sum of all XOR element of array function XorSum(arr, n) { // store result let result = 0; // Traverse array element and apply XOR // operation on it for (let i = 0; i < n; i++) { // XOR of current element with itself // according to value. let k = 0; for (let j = 1; j <= arr[i]; j++) k ^= arr[i]; result += k; } return result; } // Driver program let arr = [ 1, 2, 6, 3, 4, 5 ]; let n = arr.length; document.write(XorSum(arr, n)); </script> |
9
Time Complexity: O(n*m) (here m is the maximum element in array )
Auxiliary Space: O(1)
Efficient solution of this problem is based on the fact that if we do a XOR of any number with itself( even number of times) it produces 0 and if we do a XOR odd number of time it produces same number.
For Example
let number be : 3 do XOR with itself 3 time 3^3^3 = 3 let number be : 4 do XOR with itself 4 time 4^4^4^4 = 0 so if number is odd it's mean output is number itself. Else zero
Below is the implementation of above idea :
C++
// C++ program to compute sum of all element after // doing XOR with itself ( element_time) #include <bits/stdc++.h> using namespace std; // function return sum of all XOR element of array int XorSum( int arr[], int n) { int result = 0; for ( int i = 0; i < n; i++) { // if number is odd then add it to the // result else not if (arr[i] % 2 != 0) result += arr[i]; } return result; } // Driver program int main() { int arr[] = { 1, 2, 6, 3, 4, 5 }; int n = sizeof (arr) / sizeof (arr[0]); cout << XorSum(arr, n) << endl; return 0; } |
Java
// Java program to compute sum of // all element after doing XOR // with itself ( element_time) class GFG { // function return sum of all // XOR element of array static int XorSum( int arr[], int n) { int result = 0 ; for ( int i = 0 ; i < n; i++) { // if number is odd then add it to the // result else not if (arr[i] % 2 != 0 ) result += arr[i]; } return result; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 6 , 3 , 4 , 5 }; int n = arr.length; System.out.println(XorSum(arr, n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to compute # sum of all element after # doing XOR with itself # ( element_time) # function return sum of # all XOR element of array def XorSum(arr,n): result = 0 for i in range (n): # if number is odd then add it to the # result else not if (arr[i] % 2 ! = 0 ): result + = arr[i] return result # Driver program arr = [ 1 , 2 , 6 , 3 , 4 , 5 ] n = len (arr) print (XorSum(arr, n)) # This code is contributed # by Anant Agarwal. |
C#
// C# program to compute sum of // all element after doing XOR // with itself ( element_time) using System; class GFG { // function return sum of all // XOR element of array static int XorSum( int []arr, int n) { int result = 0; for ( int i = 0; i < n; i++) { // if number is odd then add it to the // result else not if (arr[i] % 2 != 0) result += arr[i]; } return result; } // Driver code public static void Main() { int []arr = {1, 2, 6, 3, 4, 5}; int n = arr.Length; Console.WriteLine(XorSum(arr, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to compute // sum of all element after // doing XOR with itself // ( element_time) // function return sum of // all XOR element of array function XorSum( $arr , $n ) { $result = 0; for ( $i = 0; $i < $n ; $i ++) { // if number is odd // then add it to the // result else not if ( $arr [ $i ] % 2 != 0) $result += $arr [ $i ]; } return $result ; } // Driver Code $arr = array (1, 2, 6, 3, 4, 5); $n = count ( $arr ); echo XorSum( $arr , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to compute // sum of all element after // doing XOR with itself ( element_time) // function return sum of all XOR element of array function XorSum(arr, n) { let result = 0; for (let i = 0; i < n; i++) { // if number is odd then add it to the // result else not if (arr[i] % 2 != 0) result += arr[i]; } return result; } // Driver program let arr = [ 1, 2, 6, 3, 4, 5 ]; let n = arr.length; document.write(XorSum(arr, n)); </script> |
9
Time Complexity : O(n)
Auxiliary Space : O(1)
Contact Us