Dada una array de enteros, la tarea es calcular la suma de todos los elementos de la array después de hacer XOR de cada elemento x consigo mismo x veces. Por ejemplo, si el elemento es 4, hacemos XOR de este número consigo mismo 4 veces como: = 4^4^4^4
Ejemplos:
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
Una solución simple es elegir cada elemento de la array uno por uno y hacer su XOR consigo mismo de acuerdo con su valor. Finalmente agregue valores XOR al resultado.
A continuación se muestra la implementación de la idea anterior.
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
Complejidad de tiempo: O (n * m) (aquí m es el elemento máximo en la array)
Espacio auxiliar: O (1)
La solución eficiente de este problema se basa en el hecho de que si hacemos un XOR de cualquier número consigo mismo (un número par de veces) produce 0 y si hacemos un XOR un número impar de veces produce el mismo número.
Por ejemplo
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
A continuación se muestra la implementación de la idea anterior:
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
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Este artículo es una contribución de praveen kumar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA