2178. Maximum Split of Positive Even Integers

tricky one

T: O(n)

S:O(n)

class Solution {
    public List<Long> maximumEvenSplit(long finalSum) {
        List<Long> result = new ArrayList<>();
        if (finalSum % 2 != 0) {
            return result;
        } 
        
        long i = 2L;
        long curSum = 0L;
        while (curSum + i <= finalSum) {
            result.add(i);
            curSum += i;
            i += 2L;
        }
        int lastIndex = result.size()-1;
        long lastValue = result.get(lastIndex);
        result.set(lastIndex, lastValue + finalSum - curSum);
        
        return result;
    }
}

/*
a maximum number of unique positive even integers.

even

10^10


2 4 6 8 10 12

2

4

6

8 => 20 => 8+8 =16

10 => x

*/

use greedy

O(n)

class Solution {
    public List<Long> maximumEvenSplit(long finalSum) {
        List<Long> result = new ArrayList<>();
        if (finalSum % 2 != 0) { // odd
            return result;
        }
        Long evenNumber = 2L;
        while (finalSum != 0) {
            if (finalSum - evenNumber < 0) { // at last, if ...
                Long lastEven = result.get(result.size()-1); // get last evenNumber
                result.remove(result.size()-1);
                result.add(lastEven + finalSum); // last evenNumber + remain
                break;
            }
            finalSum -= evenNumber; // 26-2, 24-4 = 20, 20-6 = 14, 14 - 8 = 6, 14 - 14 = 0
            result.add(evenNumber); // [2, 4, 6, 14]
            evenNumber += 2; 
            
        }
        return result; //[2, 4, 6, 14]
    }
}