Given an array arr[] consisting of N integers, the task is to find an integer K, not having more than maximum bits present in any array element, which when added to the array, maximizes the Bitwise XOR of the array.
Examples:
Input: N = 7, arr[] = {1, 7, 8, 11, 6, 9, 6}
Output: 3
Explanation:
Bitwise XOR of the given array = 1 ^ 7 ^ 8 ^ 11 ^ 6 ^ 9 ^ 6 = 12
(12)2 = (1100)2
(0011)2 = (3)10 is the best option of maximizing XOR of the array.
Therefore, 12 ^ 3 = 15 is the maximum possible XOR of the given array.Input: N = 5, arr[] = {1, 2, 3, 4, 5}
Output: 6
Explanation:
Bitwise XOR of the given array = 1 ^ 2 ^ 3 ^ 4 ^ 5 = 1
(1)2 = (0001)2
(0110)2 = (6)10 is the best option of maximizing XOR of the array.
Therefore, 1 ^ 6 = 7 is the maximum possible XOR of the given array.
Approach: Follow the steps below to solve the problem:
- Calculate the Bitwise XOR of all the elements of the array
- Calculate the complement of calculated XOR of the array elements such that the number of bits in the complement is equal to the maximum bits present in any array element.
- The complement of XOR is the required value to be added to maximize the Bitwise XOR of the given array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find complement of an integerunsigned int onesComplement(unsigned int n, int maxElement){ // Count the number of bits of maxElement int bits = floor(log2(maxElement)) + 1; // Return 1's complement return ((1 << bits) - 1) ^ n;}// Function to find the value required to be// added to maximize XOR of the given arrayint findNumber(int arr[], int n){ // Stores the required value // to be added to the array unsigned int res = 0; // Stores the maximum array element int maxElement = 0; // Traverse the array for (int i = 0; i < n; i++) { // Update XOR of the array res = res ^ arr[i]; // Find maximum element in array if (maxElement < arr[i]) maxElement = arr[i]; } // Calculate 1s' complement res = onesComplement(res, maxElement); // Return the answer return (res);}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); cout << findNumber(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;import java.io.*; import java.lang.*; class GFG{ // Function to find complement of an integerstatic int onesComplement(int n, int maxElement){ // Count the number of bits of maxElement int bits = (int)Math.floor(( Math.log(maxElement) / Math.log(2))) + 1 ; // Return 1's complement return ((1 << bits) - 1) ^ n;} // Function to find the value required to be// added to maximize XOR of the given arraystatic int findNumber(int arr[], int n){ // Stores the required value // to be added to the array int res = 0; // Stores the maximum array element int maxElement = 0; // Traverse the array for(int i = 0; i < n; i++) { // Update XOR of the array res = res ^ arr[i]; // Find maximum element in array if (maxElement < arr[i]) maxElement = arr[i]; } // Calculate 1s' complement res = onesComplement(res, maxElement); // Return the answer return (res);} // Driver Codepublic static void main(String[] args){ int arr[] = { 1, 2, 3, 4, 5 }; int N = arr.length; System.out.print(findNumber(arr, N));}}// This code is contributed by sanjoy_62 |
Python3
# Python program for the above approachimport math # Function to find complement of an integerdef onesComplement(n, maxElement) : # Count the number of bits of maxElement bits = math.floor(math.log2(maxElement)) + 1 # Return 1's complement return ((1 << bits) - 1) ^ n# Function to find the value required to be# added to maximize XOR of the given arraydef findNumber(arr, n) : # Stores the required value # to be added to the array res = 0 # Stores the maximum array element maxElement = 0 # Traverse the array for i in range(n): # Update XOR of the array res = res ^ arr[i] # Find maximum element in array if (maxElement < arr[i]): maxElement = arr[i] # Calculate 1s' complement res = onesComplement(res, maxElement) # Return the answer return (res) # Driver Codearr = [ 1, 2, 3, 4, 5 ]N = len(arr)print(findNumber(arr, N))# This code is contributed by code_hunt. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find complement of an integerstatic int onesComplement(int n, int maxElement){ // Count the number of bits of maxElement int bits = (int)Math.Floor(( Math.Log(maxElement) / Math.Log(2))) + 1 ; // Return 1's complement return ((1 << bits) - 1) ^ n;} // Function to find the value required to be// added to maximize XOR of the given arraystatic int findNumber(int[] arr, int n){ // Stores the required value // to be added to the array int res = 0; // Stores the maximum array element int maxElement = 0; // Traverse the array for(int i = 0; i < n; i++) { // Update XOR of the array res = res ^ arr[i]; // Find maximum element in array if (maxElement < arr[i]) maxElement = arr[i]; } // Calculate 1s' complement res = onesComplement(res, maxElement); // Return the answer return (res);} // Driver Codepublic static void Main(){ int[] arr = { 1, 2, 3, 4, 5 }; int N = arr.Length; Console.Write(findNumber(arr, N));}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// JavaScript program for above approach// Function to find complement of an integerfunction onesComplement(n, maxElement){ // Count the number of bits of maxElement let bits = Math.floor(( Math.log(maxElement) / Math.log(2))) + 1 ; // Return 1's complement return ((1 << bits) - 1) ^ n;} // Function to find the value required to be// added to maximize XOR of the given arrayfunction findNumber(arr, n){ // Stores the required value // to be added to the array let res = 0; // Stores the maximum array element let maxElement = 0; // Traverse the array for(let i = 0; i < n; i++) { // Update XOR of the array res = res ^ arr[i]; // Find maximum element in array if (maxElement < arr[i]) maxElement = arr[i]; } // Calculate 1s' complement res = onesComplement(res, maxElement); // Return the answer return (res);}// Driver Code let arr = [ 1, 2, 3, 4, 5 ]; let N = arr.length; document.write(findNumber(arr, N));// This code is contributed by avijitmondal1998.</script> |
Output:
6
Time Complexity: O(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!
