Find a number which give minimum sum when XOR with every number of array of integers | C ++ implementation of the approach ; Function to find an integer X such that the sum of all the array elements after getting XORed with X is minimum ; Finding Maximum element of array ; Find Maximum number of bits required in the binary representation of maximum number so log2 is calculated ; Running loop from p times which is the number of bits required to represent all the elements of the array ; If the bits in same position are set then count ; If count becomes greater than half of size of array then we need to make that bit '0' by setting X bit to '1' ; Again using shift operation to calculate the required number ; Calculate minimized sum ; Print solution ; Driver code
#include <bits/stdc++.h> NEW_LINE #include <cmath> NEW_LINE using namespace std ; void findX ( int arr [ ] , int n ) { int * itr = max_element ( arr , arr + n ) ; int p = log2 ( * itr ) + 1 ; int X = 0 ; for ( int i = 0 ; i < p ; i ++ ) { int count = 0 ; for ( int j = 0 ; j < n ; j ++ ) { if ( arr [ j ] & ( 1 << i ) ) { count ++ ; } } if ( count > ( n / 2 ) ) { X += 1 << i ; } } long long int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += ( X ^ arr [ i ] ) ; cout << " X ▁ = ▁ " << X << " , ▁ Sum ▁ = ▁ " << sum ; } int main ( ) { int arr [ ] = { 2 , 3 , 4 , 5 , 6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findX ( arr , n ) ; return 0 ; }