September Challenge 2021 Division 3: XOR Equal

Gangzhaorige Li — Tue, 07 Sep 2021 07:30:56 +0000

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)

Merge Two Sorted Arrays

Gangzhaorige Li — Mon, 06 Sep 2021 22:26:16 +0000

BruteForce.

Straight forward solution.
Time complexity O(nlogn).
Space complexity O(n).
Where n is total numbers from arr1 and arr2.
Idea: Combine both arrays and sort them.

Create a new array(mergedArray) with size of arr1.length + arr2.length
Add all numbers from arr1 and arr2 into mergedArray.
Use library Arrays.sort(mergedArray) to sort the array.
Return the mergedArray.

/** 
 * Merge two sorted array
 * BruteForce Time Complexity O(nlogn) Space Complexity O(n) where n is the sum of the arr1 and arr2 size
 * @param arr1 the first sorted array
 * @param arr2 the second sorted array
 * @return int[] merged sorted array from arr1 and arr2
 */
public static int[] mergeArraysUsingSort(int[] arr1, int[] arr2) {
    int n = arr1.length;
    int m = arr2.length;
    int writer = 0;
    int[] mergedArray = new int[n + m];
    // Add all nums from arr1 to mergedArray
    for(int num : arr1) {
        mergedArray[writer++] = num;
    }
    // Add all nums from arr2 to mergedArray
    for(int num : arr2) {
        mergedArray[writer++] = num;
    }
    Arrays.sort(mergedArray);
    return mergedArray;
}

Optimal solution.

Time complexity O(n).
Space complexity O(n).
Where n is total numbers from arr1 and arr2.
Since the given arr1 and arr2 were already sorted, we can take advantage of it.
Idea: Create an empty array with the combined length of both arrays. Loop from left to right compare value and store the minimum to the new array.

Create a new array(mergedArray) with size of arr1.length + arr2.length
Create three variables with index 0: writer, readerOne, and readerTwo. Writer is for writing value to mergedArray. ReaderOne and ReaderTwo both getting values from their respective array.

While there is value to read we are writing the value to mergedArray. There are 2 scenarios to handle.

First: readerOne and readerTwo both have values to read.

* Compare both values. Store the minimum value into the mergedArray.
* Increment both minimum reader and writer index by 1

Second: either readerOne or readerTwo has a value to read.

* Store the available value to mergedArray
* Increment both available reader and writer index by 1

Return the mergedArray

/** 
 * Merge two sorted array
 * Time Complexity O(n + m) Space Complexity O(n + m) where n 
is the size of arr1 and m is the size of arr2
 * @param arr1 the first sorted array
 * @param arr2 the second sorted array
 * @return int[] merged sorted array from arr1 and arr2
 */
public static int[] mergeArrays(int[] arr1, int[] arr2) {
    int n = arr1.length;
    int m = arr2.length;
    int[] mergedArray = new int[n + m];
    int readerOne = 0;
    int readerTwo = 0;
    int writer = 0;
    while(readerOne < n || readerTwo < m) {
        // Scenario 2
        // Handle Scenario 2 first because Scenario 1 might be out of index. 
        if(readerOne >= n) {
            mergedArray[writer++] = arr2[readerTwo++];
        } else if (readerTwo >= m) {
            mergedArray[writer++] = arr1[readerOne++];
        } else {
            // Scenario 1
            if(arr1[readerOne] < arr2[readerTwo]) {
                mergedArray[writer++] = arr1[readerOne++];
            } else {
                mergedArray[writer++] = arr2[readerTwo++];
            }
        }
     }
     return mergedArray;
 }

LEETCODE

Given two sorted array nums1 and nums2. Merge the nums2 into nums1. Nums1 will have enough space to store nums2.

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

The idea is similar as above, but we are doing opposite. Instead of storing minimum value to the left side we are storing the maximum value to the right side of nums1 until either readerOne or readerTwo reaches out of index.

Note: If readerTwo is not out index means these remaining values are the smallest, therefore just write them directly to nums1.
Since we are directly modifying the array nums1, so space complexity is O(1).

/** 
 * Merge two sorted array LeetCode Problem 
 * Link: https://leetcode.com/problems/merge-sorted-array
 * Time Complexity O(n + m) Space Complexity O(1) where n is the size of nums1 and m is the size of nums2
 * @param nums1 sorted array with enough space to fill nums2 
 * @param m original size of the nums1
 * @param nums2 sorted array that needs to be combined to nums1
 * @param n the size of the nums2
 */
public void mergeArraysLeetCode(int[] nums1, int m, int[] nums2, int n) {
    int writer = nums1.length - 1;
    int readerOne = m - 1;
    int readerTwo = n - 1;
    while(readerOne >= 0 && readerTwo >= 0){
        if(nums1[readerOne] < nums2[readerTwo]){
            nums1[writer] = nums2[readerTwo--];
        } else {
            nums1[writer] = nums1[readerOne--];
        }
        writer--;
    }
    // Add remaning nums from nums2 to nums1. These values are smallest.
    while(readerTwo >= 0){
        nums1[writer--] = nums2[readerTwo--];
    }
}

Forem: Gangzhaorige Li