Find a value X in range [0, K] which can maximize X XOR sum over given array
Given an array a[] of size N and an integer K, the task is to find a value X in the range [0, K] which can maximize the value of the given function
- Xor-sum(X) = (X XOR A[0]) + (X Xor A[1]) + (X Xor A[2]) + __________+ (X Xor A[N-1]).
Examples:
Input: a[] = {1, 2, 3, 4, 5, 6}, N=6, K=10
Output: 8
Explanation: The value of X is 1 for which the required sum becomes maximum.Input: a[] = {1, 6}, N=2, K=7
Output: 0
Approach: The idea is to consider each and every value of K and then find the value of X which satisfies the above condition. Follow the steps below to solve the problem:
- Initialize the variables max and X as 0 and -1 to store the maximum sum defined and the value of X for which it is happening.
- Iterate over the range [0, K] using the variable j and perform the following tasks:
- Initialize the variable sum as 0 to store the defined sum.
- Iterate over the range [0, N) using the variable i and perform the following tasks:
- Set the value of sum as sum + j^a[i].
- If sum is greater than max, then set the value of max as sum and X as j.
- After performing the above steps, print the value of X as the answer.
Below is the implementation of the above approach
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the value of X for which // the given sum maximises void findValue(vector< int >& a, int N, int K) { // Variables to store the maximum // sum and that particular value // of X. long long int max = 0, X = -1; // Check every value of K for ( int j = 0; j <= K; j++) { // Variable to store the desired sum long long int sum = 0; for ( int i = 0; i < N; i++) { (sum = sum + (j ^ a[i])); } // Check the condition if (sum > max) { max = sum; X = j; } } // Print the result cout << X; } // Driver Code int main() { vector< int > a = { 1, 2, 3, 4, 5, 6 }; int N = 6, K = 10; findValue(a, N, K); return 0; } |
C
// C program for the above approach #include <stdio.h> // Function to find the value of X for which // the given sum maximises void findValue( int *a, int N, int K) { // Variables to store the maximum // sum and that particular value // of X. long long int max = 0, X = -1; // Check every value of K for ( int j = 0; j <= K; j++) { // Variable to store the desired sum long long int sum = 0; for ( int i = 0; i < N; i++) { (sum = sum + (j ^ a[i])); } // Check the condition if (sum > max) { max = sum; X = j; } } // Print the result printf ( "%lli" , X); } // Driver Code int main() { int a[] = { 1, 2, 3, 4, 5, 6 }; int N = 6, K = 10; findValue(a, N, K); return 0; } // This code is contributed by palashi. |
Java
// Java program for the above approach class GFG { // Function to find the value of X for which // the given sum maximises public static void findValue( int [] a, int N, int K) { // Variables to store the maximum // sum and that particular value // of X. int max = 0 , X = - 1 ; // Check every value of K for ( int j = 0 ; j <= K; j++) { // Variable to store the desired sum int sum = 0 ; for ( int i = 0 ; i < N; i++) { sum = sum + (j ^ a[i]); } // Check the condition if (sum > max) { max = sum; X = j; } } // Print the result System.out.println(X); } // Driver Code public static void main(String args[]) { int [] a = { 1 , 2 , 3 , 4 , 5 , 6 }; int N = 6 , K = 10 ; findValue(a, N, K); } } // This code is contributed by saurabh_jaiswal. |
Python3
# Python3 program for the above approach # Function to find the value of X for which # the given sum maximises def findValue(a, N, K) : # Variables to store the maximum # sum and that particular value # of X. max = 0 ; X = - 1 ; # Check every value of K for j in range ( K + 1 ) : # Variable to store the desired sum sum = 0 ; for i in range (N) : sum = sum + (j ^ a[i]); # Check the condition if ( sum > max ) : max = sum ; X = j; # Print the result print (X); # Driver Code if __name__ = = "__main__" : a = [ 1 , 2 , 3 , 4 , 5 , 6 ]; N = 6 ; K = 10 ; findValue(a, N, K); # This code is contributed by AnkThon |
C#
// C# program for the above approach using System; public class GFG { // Function to find the value of X for which // the given sum maximises public static void findValue( int [] a, int N, int K) { // Variables to store the maximum // sum and that particular value // of X. int max = 0, X = -1; // Check every value of K for ( int j = 0; j <= K; j++) { // Variable to store the desired sum int sum = 0; for ( int i = 0; i < N; i++) { sum = sum + (j ^ a[i]); } // Check the condition if (sum > max) { max = sum; X = j; } } // Print the result Console.WriteLine(X); } // Driver Code public static void Main( string []args) { int [] a = { 1, 2, 3, 4, 5, 6 }; int N = 6, K = 10; findValue(a, N, K); } } // This code is contributed by AnkThon |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the value of X for which // the given sum maximises function findValue(a, N, K) { // Variables to store the maximum // sum and that particular value // of X. let max = 0, X = -1; // Check every value of K for (let j = 0; j <= K; j++) { // Variable to store the desired sum let sum = 0; for (let i = 0; i < N; i++) { (sum = sum + (j ^ a[i])); } // Check the condition if (sum > max) { max = sum; X = j; } } // Print the result document.write(X); } // Driver Code let a = [1, 2, 3, 4, 5, 6]; let N = 6, K = 10; findValue(a, N, K); // This code is contributed by Potta Lokesh </script> |
Output
8
Time Complexity: O(K*N)
Auxiliary Space: O(1)