Maximum Split of Positive Even Integers LeetCode solution in C++

1
class Solution {
2
 public:
3
  using ll = long long;
4

5
  ll bs(ll low, ll high, ll fs) {
6
    ll ans = 1;
7
    while (low <= high) {
8
      ll mid = low + (high - low) / 2;
9
      if (mid * (mid + 1) > fs) {
10
        high = mid - 1; // If sum till index equal to 'mid' > fs then make high = mid-1
11
      } else if (mid * (mid + 1) == fs) {
12
        return mid; // If sum till index equal to 'mid == fs, return 'mid'
13
      } else {
14
        ans = mid;     // If sum till index equal to 'mid' < fs, update answer
15
        low = mid + 1; // check for better answer
16
      }
17
    }
18
    return ans;
19
  }
20

21
  vector<long long> maximumEvenSplit(long long finalSum) {
22
    // ****some base cases / corner cases****
23
    if (finalSum & 1) return {};
24
    if (finalSum == 4) return {4};
25
    if (finalSum == 8) return {2, 6};
26

27
    vector<ll> ans;
28

29
    // assume that we are giving indices to even numbers
30
    // EVEN NUMBERS -> 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 ..............
31
    // THEIR INDICES-> 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ..............
32

33
    // 'idx' is the index of that EVEN number uptil which the total sum of all
34
    // even numbers <= finalSum
35
    ll idx = bs(1, finalSum / 2, finalSum);
36

37
    // Consequently, 'end' is that EVEN number uptil which the total sum of all
38
    // even numbers <= finalSum
39
    ll start = 2, end = idx * 2;
40

41
    // Now, we add all the even numbers from index 1 to index 'idx-1'
42
    //  2 + 4 + 6 + 8 ........................... + (end-2) + end
43
    //  1 2 3 4 ........................... idx-1 idx
44
    for (int i = start; i <= (idx - 1) * 2; i += 2) {
45
      ans.push_back(i);
46
    }
47

48
    // We do not add the last even number yet, so that we can modify it and add
49
    // it later to make the (totalSumSoFar) == finalSum 'totalSumSoFar' can be
50
    // easily calculated by using the formula ( totalSumSoFar = idx*(idx+1) )
51

52
    // increasing the last even number 'end' by the difference of (finalSum and
53
    // totalSumSoFar)
54
    if (idx * (idx + 1) < finalSum) {
55
      end = end + abs(finalSum - idx * (idx + 1));
56
    }
57

58
    // adding the last even number after increasing it with the required factor
59
    ans.push_back(end);
60
    return ans;
61
  }
62
};