Minimum Bitwise OR operations to make any two array elements equal

Ishaan Ahuja -

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Given an array of integers and an integer K, we can perform the Bitwise OR operation between K and elements of the array any number of times.

We have to count minimum number of such operations that are required to make any two elements of the array equal. If, even after performing such operations, it is not possible to make any two elements of the array equal, then print "Not Possible".

Examples:

Example Input 1:
K = 4
n = 5
arr = [1, 1, 2, 2, 3]
Example Output 1:
Minimum Operations are: 0
(Since we already have equal elements in the array)

Example Input 2:
K = 3
n = 3
arr = [100, 1000, 10000]
Example Output 2:
Not Possible
(Since we cannot make any two elements equal in this array by performing any number of given operations)

Let's first understand the use of BITWISE OR OPERATOR
Bitwise OR is a binary operator which is denoted by |. It operates on two operands.
The | operator compares corresponding bits of two operands. If either of the bits is 1, it gives 1. If not, it gives 0. For example,

For example:

23 = 00010111 (In Binary)
15 = 00001111 (In Binary)

Bitwise OR Operation of 12 and 25
  00010111
| 00001111
  ________
  00011111  = 31 (In decimal)

Points to Note:

  • The associativity of Bitwise OR operator is form left to right.
  • The result of Bitwise OR operator is 1 if any of the two bits is 1.

Approach towards the Algorithm:
An observation made here is that if it is possible to do such an operation which can result in an array having two elements equal, then the minimum number of operations would be either 0, 1 or 2.
Here's why:
Consider performing Bitwise OR operation on a number 'a' with k which give result as c. a | k = c. Now, we can perform c | k any number of times but it will yield the same result.

  • The output will be 0, if we pass an array arr which already has two or more equal elements in it.
  • If arr does not contain equal elements, we will create a new array subArr which will hold subArr[i] = (arr[i] | K) for every index i.
    Now, for each element in arr, we will check if there is any index j such that i != j and arr[i] equals subArr[j].
    If such a condition exits, then the output will be 1.
  • If the above mentioned condition is not met, we will check for an index i in the new array subArr,
    such that there is any index j where i != j and subArr[i] equals subArr[j].
    If such a condition exits, then the output will be 2.
  • If none of the above conditions are satisfied, then we cannot find make any two elements in the array equal and hence, output will be -1.

Steps to be followed:

  • Ask the user to input K, size and all elements of the array.
  • Then, we will create a function minOperations which accepts 3 parameters: the array, the size of the array and K.
  • In the function, we declare a HashMap map of Integer as keys and Boolean as values.
  • We will add all elements of array as keys of the map. While adding, we will continue to check if the element to be added is already present in the map. In this case, we return 0.
  • Next step involves creating a modified copy(subArr) of the original array where every element of the subArr equals arr[i] | K for every i(index of original array elements).
  • Add all elemets of subArr to the map which are distinct from elements of the original array. Now, if map contains a duplicate, return 1.
  • If not, check if map contains any element of subArr. If it contains an element from the subArr, return 2.
  • If none of the above conditions satisfy, it is not possible to have equal elements in the array.

Example
Let us walkthrough an example to understand these steps.

  • Consider arr = [1, 9, 4, 3] and K = 5.
  • We put all these elements in a HashMap. Since no duplicates are found in this array, we move to the next step.
  • Create a new subArr where every element of the equals arr[i] | K.
  • The new array for this example is SubArr = [5, 13, 5, 7].
  • We now put 5, 13, 5 and 7 in the HashMap, since these are numbers changed after performing the OR operation.
  • Since we get a duplicate in the array after exactly one operation, the output for this program will be 1.

Code for the Algorithm:

import java.util.Scanner; 
import java.util.Map; 
import java.util.HashMap; 
  
class Test { 
      
    /**
     * Returns minimum  number of operations to make any two array elements equal
     * @param  arr  an array containing input elements by the user 
     * @param  n    the size of the input array
     * @param  K    integer with which Bitwise OR operation has to be performed
     * @return      minimum Bitwise OR operations
     */
    public static int minOperations(int[] arr, int n, int K) { 
  
        Map<Integer, Boolean> map = new HashMap<>(); 
  
        for (int i = 0; i < n; i++) {
            // Check for the first condition
            // if the array already has equal elements
            if (map.containsKey(arr[i])) { 
                return 0;
            } else {
                map.put(arr[i], true);
            } 
        } 
        
        // If the above condition is not true
        // Create new array with OR operations 
        int[] subArr = new int[n]; 
        for (int i = 0; i < n; i++) { 
            subArr[i] = arr[i] | K;
        }
  
        map.clear(); 
  
        // Check for condition two
        for (int i = 0; i < n; i++) { 
  
            // If Bitwise OR operation between 
            // 'K' and arr[i] gives 
            // a number other than arr[i] 
            if (arr[i] != subArr[i]) { 
                map.put(subArr[i], true);
            } 
        } 
   
        // Check if condition two is satisfied
        for (int i = 0; i < n; i++) { 
        
            // if even a single elements becomes equal
            if (map.containsKey(arr[i])) 
                return 1; 
        } 
  
        map.clear(); 
  
        // Check for the third condition
        for (int i = 0; i < n; i++) { 
  
            // Check if the sub array contains duplicates 
            if (map.containsKey(subArr[i])) 
                return 2; 
            map.put(subArr[i], true); 
        } 
        
        // If none of the above conditions are satisfied
        // then it is impossible to make any array elements equal
        // using Bitwise OR operation 
        return -1; 
    } 
  
    public static void main(String[] args) { 
        Scanner scan = new Scanner(System.in);
        int K = 4;
        
        System.out.println("Please enter size of the array");
        int n = scan.nextInt();
        
        int[] arr = new int[n];
        System.out.println("Please enter " + n + " elements to the array");
        for(int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        
        int min = minOperations(arr, n, K);
        if(min == -1) {
            System.out.println("Not Possible");
        } else {
            System.out.println("Minimum Operations are: " + min);
        }
    } 
}

Sample Test Cases:

Sample 1

Input:
 K = 4
 n = 5
 arr = [1, 2, 3, 4, 5]
Output:
 Minimum Operations are: 1

Sample 2

Input:
 K = 7
 n = 10
 arr = [0, 5, 6, 3, 2, 1, 9, 4, 7, 8]
Output:
 Minimum Operations are: 1

TIME COMPLEXITY
The Time Complexity of the above algorithm is O(n). The operations on the HashMap such as containsKey and put take O(1) Time.

With this article at OpenGenus, you must have the complete idea of finding the Minimum Bitwise OR operations to make any two array elements equal. Enjoy.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.