You are given an array A consisting of N integers and an integer X. Your goal is to have as many equal integers as possible in the array. To achieve this goal, you can do the following operation:
- Choose an index i (1≤i≤N) and set Ai=Ai⊕X, where ⊕ denotes the bitwise xor operation.
Find the maximum number of equal integers you can have in the final array and the minimum number of operations to obtain these many equal integers.
Constraint:
- 0 ≤ X ≤ 10^9
- 0 ≤ Ai ≤ 10^9
Input: x = 2, arr = [1,2,3]
Output: [2,1]
One way to obtain 2 equal integers is to set A1=A1⊕2 =1⊕2=3.
So the array becomes [3,2,3].
There is no way to obtain 3 equal integers in the final array.
The important part of this problem is to keep track of number of occurrence of each number and number of operation required for the number. Therefore, we are going to use two HashMap.
We are mapping number with occurrence and number with operations.
Suppose our array would look like [1,2,3] then at the beginning our maps would look like the following.
Counter {1:1,2:1,3:1}
Operations {1:0,2:0,3:0}
The next step is to loop our array and convert each number with the given XOR value, then update the counter and operations accordingly.
Note:
- A XOR B = C
- A XOR A = 0
- A XOR 0 = A
- 0 XOR A = A
It is important to notice that A XOR 0 = A. Therefore it does not change the current number while O XOR A = A changes the current number.
- A XOR 0 = A. Original value is A. Modified value is still A.
- O XOR A = A. Original value is O. Modified value is A.
In the conclusion, A XOR 0 should not update our maps at all.
Example:
We read the first element in our array which is 1.
1 XOR 2 gives us 3.
Since 3 is already in our counters then update num of counter.
Since 3 is already in our operations then update num of operations.
Counter {1:1, 2:1, 3:2}
Operations {1:0, 2:0, 3:1}
Once we are done with the loops. All we have to do is find the max occurrence inside our counter.
Note: there could be multiple max occurrence.
From those we have to find the min operations.
That would be our result.
Let's code it out.
public static int[] findMax(int x, int[] arr) {
HashMap<Integer,Integer> counter = new HashMap<>();
HashMap<Integer,Integer> operations = new HashMap<>();
for(int num: arr) {
// count num of occurrence
counter.put(num, counter.getOrDefault(num, 0) + 1);
// initially there is 0 operation.
operations.put(num, 0);
}
for(int num: arr) {
// Special case where it does not give us a new number.
if(x == 0) {
break;
}
int xorResult = num ^ x;
// update counter and operations.
counter.put(xorResult, counter.getOrDefault(xorResult, 0) + 1);
operations.put(xorResult, operations.getOrDefault(xorResult, 0) + 1);
}
List<Integer> list = new ArrayList<>();
int max = 1;
// Finding all numbers with greatest occurrences.
for(Map.Entry<Integer, Integer> entry: counter.entrySet()){
if(max < entry.getValue()) {
max = entry.getValue();
list.clear();
list.add(entry.getKey());
} else if (max == entry.getValue()){
list.add(entry.getKey());
}
}
int minOperation = Integer.MAX_VALUE;
// Choose the lowest operations.
for(int num: list) {
minOperation = Math.min(minOperation, operations.get(num));
}
return new int[]{max, minOperation};
}
Time & Space Complexity
Time complexity O(n + n + n + n) = O(4n) = O(n)
Space complexity O(n + n) = O(2n) = O(n)
Top comments (0)