Get this book -> Problems on Array: For Interviews and Competitive Programming

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.