Most Intuitive Solution!!! [Easy to Understand]
IntuitionThe problem is about finding the largest outlier in an array. An outlier is defined as an element that, when removed, makes the sum of the remaining el
# Intuition
The problem is about finding the largest outlier in an array. An outlier is defined as an element that, when removed, makes the sum of the remaining elements even. We can solve this problem by iterating through the array and checking each element to see if it meets the criteria.

# Approach
1. **Calculate the total sum**: First, calculate the total sum of all elements in the array.
2. **Use a frequency map**: Create a frequency map to store the count of each element in the array.
3. **Iterate through the array**: For each element in the array:
   - Calculate the remaining sum by subtracting the current element from the total sum.
   - Check if the remaining sum is even.
   - If it is, check if the remaining sum divided by 2 exists in the frequency map.
   - If it does, update the largest outlier.
4. **Return the largest outlier**: After iterating through the array, return the largest outlier found.

### Example
Consider the array `a = [1, 2, 3, 4, 5]`:
1. Calculate the total sum: `ts = 1 + 2 + 3 + 4 + 5 = 15`.
2. Create a frequency map: `{1: 1, 2: 1, 3: 1, 4: 1, 5: 1}`.
3. Iterate through the array:
   - For element 1: `rs = 15 - 1 = 14` (even), `ele = 14 / 2 = 7` (not in the map).
   - For element 2: `rs = 15 - 2 = 13` (odd), skip.
   - For element 3: `rs = 15 - 3 = 12` (even), `ele = 12 / 2 = 6` (not in the map).
   - For element 4: `rs = 15 - 4 = 11` (odd), skip.
   - For element 5: `rs = 15 - 5 = 10` (even), `ele = 10 / 2 = 5` (in the map), update outlier to 5.
4. The largest outlier is 5.


# Complexity
- Time complexity: $$O(n)$$, where $$n$$ is the length of the array, since we iterate through the array twice.
- Space complexity: $$O(n)$$, as we are using a frequency map to store the count of each element.

# Code
```java
class Solution {
    public int getLargestOutlier(int[] a) {
        int ts = 0;
        Map<Integer, Integer> freq = new HashMap<>(a.length);
        for (int i : a) {
            ts += i;
            freq.put(i, freq.getOrDefault(i, 0) + 1);
        }

        int out = Integer.MIN_VALUE;
        for (int i : a) {
            int rs = ts - i;
            if (rs % 2 != 0) continue;

            freq.put(i, freq.getOrDefault(i, 0) - 1);
            int ele = rs / 2;

            if (freq.getOrDefault(ele, 0) > 0) out = Math.max(out, i);
            freq.put(i, freq.get(i) + 1);
        }

        return out;
    }
}

['Math', 'Java']