Given an array arr[] of non-negative integers where arr[i] >= 0, the task is to select a non-negative integer ‘k’ and perform the bitwise-XOR operation on every element of the array with ‘k’ (i.e., XOR0 = arr[0] ^ k, XOR1 = arr[1] ^ k, and so on). The objective is to minimize the bitwise-OR of the resulting array, specifically to choose ‘k’ in such a way that the value of XOR0 | XOR1 | XOR2 | … | XORn-1 is minimized.
Examples:
Input: n = 3, arr[] = {3, 5, 7}
Output: 6
Explanation: 3 = 011, 5 = 101, 7 = 111, k is chosen as 1(001), 3^k = 2(010), 5^k = 4(100) and 7^k = 6(110). Now take the bitwise OR of 2, 4, and 6 which equals 6.Input: n = 4, arr[] = {4, 8, 10, 0}
Output: 14
Explanation: 4 = 100, 8 = 1000, 10 = 1010, 0 = 00, k is chosen as 0, 4^k = 4, 8^k = 8, 10^k = 10, 0^k = 0, The bitwise OR of 4, 8, 10, and 0 is 14
Approach: To solve the problem follow the below idea:
The idea behind this approach is that since we want to minimize Bitwise-OR(ans), it should have 0’s as many places as possible. It is known that bitwise OR is zero only when all bits at that position are 0, hence k should be chosen such that for maximum bit positions, XORi has 0 for all i.
Observations:
- For all i, arr[i] has its bit as 1 -> the bit of k will be 1, since 1^1 = 0
- For all i, arr[i] has its bit as 0 -> the bit of k will be 0, since 0^0 = 0
- For some i, arr[i] has it’s bits 1 and others have bit 0 -> the bit of k can be taken either 0 or 1, it won’t matter, because in this case, it is impossible to make XORi 0 for all i, since 1^0=1 and 0^1=1.
- To choose k, there are 3 cases. If at a particular bit position:
To get a clear understanding why this is impossible, see the example below:
- arr[] = {4, 6, 3}, lets consider the bits at the leftmost position for all numbers. [4(100)->1, 6(110)->1, 3(011)->0].
- If we chose bit of k at this position to be 1 then XOR for 4 -> 1^1 = 0, 6 -> 1^1 = 0, 3 -> 0^1 = 1.
- This makes it clear that if at a particular position the bits in the elements of the array nums are a combination of 1’s and 0’s then it is not possible to get XORi as 0 for all i. The bit of k is taken as 0 in the implementation below, since any one of 1 or 0 can be taken
- If we take the bit for k at this position to be 0, then XOR for 4 -> 1^0 = 1, 6 -> 1^0 = 1, 3 -> 0^0 = 0.
Follow the steps to solve the problem:
- Iterate through a loop of 32 bit positions(considering the maximum value of arr[i] to be 2^31)
- For every position, count the number of set bits for all elements of arr.
- If this count equals the size of array arr, then the bit of k for that position is 1, for all other cases the bit of k is 0.
- Now, that we have found k, Using a for loop, take the XOR of every element of arr with k and then take the bitwise OR of the resulting values
Below is the C++ implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;int minimum_or(int n, vector<int>& nums){ // Making a copy of array nums in temp vector<int> temp = nums; // The integer with which we XOR every // element of the array nums int k = 0; // Loop to visit every bit position // of elements of nums for (int bit = 0; bit < 32; bit++) { int count = 0; for (int i = 0; i < n; i++) { // Check if the bit is set if (temp[i] & 1) count++; temp[i] >>= 1; } // If bit at index i is set for all elements of nums // then the bit of k is set if (count == n) k = k + (int)pow(2, bit); } int XOR = 0; int ans = 0; // loop to compute the bitwise-OR for (int i = 0; i < n; i++) { // compute bitwise-xor of an element with k XOR = nums[i] ^ k; ans = ans | XOR; } return ans;}// driver's codeint main(){ int n; n = 3; vector<int> nums = { 4, 3, 6 }; // function call cout << minimum_or(n, nums); return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG { public static int minimumOr(int n, List<Integer> nums) { // Making a copy of array nums in temp List<Integer> temp = new ArrayList<>(nums); // The integer with which we XOR every // element of the array nums int k = 0; // Loop to visit every bit position // of elements of nums for (int bit = 0; bit < 32; bit++) { int count = 0; for (int i = 0; i < n; i++) { // Check if the bit is set if ((temp.get(i) & 1) == 1) count++; temp.set(i, temp.get(i) >> 1); } // If bit at index i is set for all elements of // nums // then the bit of k is set if (count == n) k = k + (int)Math.pow(2, bit); } int XOR = 0; int ans = 0; // loop to compute the bitwise-OR for (int i = 0; i < n; i++) { // compute bitwise-xor of an element with k XOR = nums.get(i) ^ k; ans = ans | XOR; } return ans; } // Driver code public static void main(String[] args) { int n = 3; List<Integer> nums = new ArrayList<>(); nums.add(4); nums.add(3); nums.add(6); // Function call System.out.println(minimumOr(n, nums)); }} |
Python3
# Python code for the above approachdef minimum_or(n, nums): # Making a copy of the array nums in temp temp = nums[:] # The integer with which we XOR every element of the array nums k = 0 # Loop to visit every bit position of elements of nums for bit in range(32): count = 0 for i in range(n): # Check if the bit is set if temp[i] & 1: count += 1 temp[i] >>= 1 # If bit at index i is set for all elements of nums, # then the bit of k is set if count == n: k += 2 ** bit XOR = 0 ans = 0 # Loop to compute the bitwise-OR for i in range(n): # Compute bitwise-xor of an element with k XOR = nums[i] ^ k ans |= XOR return ans# Driver's coden = 3nums = [4, 3, 6]# Function callprint(minimum_or(n, nums)) |
C#
using System;using System.Collections.Generic;public class MinimumOR{ // Function to find the minimum Bitwise OR value public static int FindMinimumOR(int n, List<int> nums) { List<int> temp = new List<int>(nums); // Make a copy of the nums list int k = 0; // The integer with which we XOR every element of the nums list // Loop to visit every bit position of elements of nums for (int bit = 0; bit < 32; bit++) { int count = 0; for (int i = 0; i < n; i++) { // Check if the bit is set if ((temp[i] & 1) == 1) count++; temp[i] >>= 1; // Right shift by 1 to move to the next bit } // If bit at index 'bit' is set for all elements of nums, // then the corresponding bit of k is set if (count == n) k += (int)Math.Pow(2, bit); } int XOR = 0; int ans = 0; // Loop to compute the bitwise OR for (int i = 0; i < n; i++) { // Compute bitwise XOR of an element with k XOR = nums[i] ^ k; ans |= XOR; // Bitwise OR operation to get the final result } return ans; } // Main method to test the function public static void Main(string[] args) { int n = 3; List<int> nums = new List<int> { 4, 3, 6 }; // Function call Console.WriteLine(FindMinimumOR(n, nums)); }} |
Javascript
// JavaScript code for the above approach// Function to calculate the minimum // bitwise OR of elements in an arrayfunction minimumOR(n, nums) { // Make a copy of the input // array nums in temp let temp = [...nums]; // The integer with which we XOR // every element of the array nums let k = 0; // Loop to visit every bit position // of elements of nums for (let bit = 0; bit < 32; bit++) { let count = 0; for (let i = 0; i < n; i++) { // Check if the bit is set if (temp[i] & 1) { count++; } temp[i] >>= 1; } // If bit at index i is set // for all elements of nums, // then the bit of k is set if (count === n) { k += 2 ** bit; } } let XOR = 0; let ans = 0; // Loop to compute the bitwise OR for (let i = 0; i < n; i++) { // Compute bitwise XOR of an element with k XOR = nums[i] ^ k; ans |= XOR; } return ans;}// Driver codeconst n = 3;const nums = [4, 3, 6];// Function callconsole.log(minimumOR(n, nums)); |
Output
7
Time Complexity: O(32*n), where n is the length of the array
Auxiliary Space: O(n), since an array of length n is used
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!
Share your thoughts in the comments
