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 maximisesvoid 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 Codeint 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 maximisesvoid 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 Codeint 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 approachclass 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 maximisesdef 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 Codeif __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 approachusing 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)
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!
