Algorithm to Split a Number Array into Two Balanced Parts by Using Sorting and Prefix Sum

Balanced Split

Given an array of integers (which may include repeated integers), determine if there’s a way to split the array into two subarrays A and B such that the sum of the integers in both arrays is the same, and all of the integers in A are strictly smaller than all of the integers in B.
Note: Strictly smaller denotes that every integer in A must be less than, and not equal to, every integer in B.

1	bool balancedSplitExists(int[] arr)

bool balancedSplitExists(int[] arr)

Input
All integers in array are in the range [0, 1,000,000,000].

Output
Return true if such a split is possible, and false otherwise.
Example 1
arr = [1, 5, 7, 1]
output = true
We can split the array into A = [1, 1, 5] and B = [7].

Example 2
arr = [12, 7, 6, 7, 6]
output = false
We can’t split the array into A = [6, 6, 7] and B = [7, 12] since this doesn’t satisfy the requirement that all integers in A are smaller than all integers in B.

Array Balanced Split using Sort and Prefix Sum

We can sort the numbers in O(NLogN) complexity. And we also need to compute the total sum of all numbers in O(N) complexity. This can be implemented by a simple for loop or using the std::accumulate function from the algorithm header.

Then, by iterating from the smallest number to the largest, we compute the prefix sum – then we know if we split it into two parts if the sum is equal. The sum of the remaining numbers can be computed by subtracting the prefix sum from the total sum. Also, we have to rule out the same numbers in two parts by skipping the next duplicate numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

bool balancedSplitExists(vector<int>& arr){
  sort(begin(arr), end(arr));
  int sum = std::accumulate(begin(arr), end(arr), 0, [](int a, int b) {
    return a + b;
  });
  int prefix = 0;
  for (int i = 0; i + 1 < arr.size(); ++ i) {
    prefix += arr[i];
    if (arr[i] != arr[i + 1]) {
      if (sum - prefix == prefix) {
        return true;
      }
    }
  }  
  return false;
}

bool balancedSplitExists(vector<int>& arr){
  sort(begin(arr), end(arr));
  int sum = std::accumulate(begin(arr), end(arr), 0, [](int a, int b) {
    return a + b;
  });
  int prefix = 0;
  for (int i = 0; i + 1 < arr.size(); ++ i) {
    prefix += arr[i];
    if (arr[i] != arr[i + 1]) {
      if (sum - prefix == prefix) {
        return true;
      }
    }
  }  
  return false;
}

The overall complexity is O(NLogN) which is dominated by sorting process.

–EOF (The Ultimate Computing & Technology Blog) —