13

I encounter a problem to let you drop two elements in an array to make the three part's sum equal.

  Ex:
  1 2 4 3 5 2 1
  After I drop the 4 and 5, it becomes 1, 2 | 3 | 2, 1

Constraints:

  1.Numbers are all integer > 0

  2.Drop two elements in the array, so the three splitted subarrays will have same subarray sum.

I have tried it by using two pass algorithm as the following

First pass:O(n) Count the accumulated sum from the left so I can get the range sum easily.

Second pass:O(n^2) Use nested loop to get the subarray's start and end index. Then, calculate the left, mid, right sum.

// 1.get accumulated sum map
int[] sumMap = new int[A.length];
int sum = 0;
for(int i = 0; i < A.length; i ++) {
    sum += A[i];
    sumMap[i] = sum;
}

// 2.try each combination
for(int i = 1; i < A.length - 1; i ++) {
    for(int j = i + 1; j < A.length - 1; j ++) {
        int left = sumMap[i] - A[i];
        int mid = sumMap[j] - sumMap[i] - A[j];
        int right = sumMap[A.length - 1] - sumMap[j];

        if(left == mid && mid == right)return true;
    }
}

Are there any better algorithm that can achieve O(n)?

Thanks

3
  • show us what you have tried Oct 2, 2018 at 1:23
  • 2
    The problem description is very vague. You provide an example, but almost no actual mention on the constraints or requirements. Oct 2, 2018 at 1:34
  • @jason do you have the latest solution for this?
    – Danish
    Aug 8, 2019 at 9:30

3 Answers 3

24
  • Step 1: Create a sum array

  • Step 2: Follow two pointer approach

      public boolean solution(int[] A) {
    
      int leftPointer = 1;
      int rightPointer = A.length - 2;
      int leftPartSum, middlePartSum, rightPartSum;
      int[] sumArray = new int[A.length];
    
      // Initializing the sum array
      sumArray[0] = A[0];
      for(int i = 1; i < A.length; i ++)
          sumArray[i] = sumArray[i-1] +  A[i];
    
      // Using two Pointer technique
      while(leftPointer < rightPointer) {
    
          leftPartSum = sumArray[leftPointer] - A[leftPointer];
          middlePartSum = sumArray[rightPointer] - sumArray[leftPointer] - A[rightPointer];
          rightPartSum = sumArray[A.length - 1] - sumArray[rightPointer];
    
          if(leftPartSum == middlePartSum && middlePartSum == rightPartSum)
              return true;
    
          if (leftPartSum < rightPartSum)
              leftPointer++;
          else if (leftPartSum > rightPartSum)
              rightPointer--;
          else{                   // Else condition denotes: leftPartSum == rightPartSum
              leftPointer++;
              rightPointer--;
          }
      }
      return false; // If no solution is found then returning false
      }
    

Detailed Explanation:

Sum Array: In the first pass over array, count the accumulated sum from the left to right. Althought this will take O(n) time to create a sum array but this will help you in getting the leftPartSum, middlePartSum and rightPartSum in O(1) at any given time.

Two Pointer Approach: In two pointer approach, One pointer starts from the beginning while the other pointer starts from the end.

enter image description here

In this case, If we remove the first element or last element, then there is no way in which we can split the array into 3 equal parts. Hence, we can safely assume that

int leftPointer = 1; 
int rightPointer = A.length - 2;

Note: Array contains indexed from 0 to n-1;

Now, we move the pointer towards each other and at every movement we calculate leftPartSum, middlePartSum and rightPartSum. Whether we need to move left pointer or right pointer is decided by the fact that which one of the two sums (leftPartSum or rightPartSum is smaller)

4
  • Sorry but what's the purpose to move the pointer toward or forward depending the leftPArt and the rightPart? Can you explain it? Also why we can not take the first and last position instead? you say there's no way to split into 3 equal part, but why?
    – StuartDTO
    Apr 27, 2020 at 16:06
  • Please, I want to understand it, could you give me the explanation please?
    – StuartDTO
    Apr 28, 2020 at 11:11
  • @StuartDTO if you take the first element you are not leaving any element to its left, therefore the most parts you could split the array into would be 2... unless you remove the last element, then you would only have one part of the array: the middle. For example, if you take the array [2, 4, 5, 3, 3, 9, 2, 2, 2], taking the second and seventh element would leave us with three parts: [2], [5, 3, 3, 9] and [2, 2]. When you drop an element is the same as if you put an imaginary separator. A separator in the first or last place simply doesn't separe anything.
    – danielsto
    Jul 13, 2020 at 16:27
  • without extra space you can use this with the same array just need to calculate the sum, divide the sum by three and each part can't exceed the sum/3 value, left pointer can be increased by one each time and right pointer should be decreased by each pointer. Once the subSum overflows that is the break part. if leftSum == rightSum we just need to check sum for middle between {leftPointer+1 --- rightPointer-1}, if that is also same return true else false. Which will become same to the accepted answer eventually once instead of taking sum we are directly multiplying it by 3
    – Mr X
    Jul 17, 2020 at 6:56
12

Assuming that first and last element can't be dropped and all elements are >0:

Set a variable sumleft to value of first element, sumright to value of last element. You also need index variables to remember which elements from left and right were already added to the sums.

  1. If sumleft == sumright, test if next elements from left and right can be dropped to fulfill requirement. If so -> done. If not take next elements from left and right and add it to the respective sum variable. Back to 1.

  2. If sumleft < sumright, add next value from the left to sumleft. Back to 1.

  3. If sumleft > sumright, add next value from the right to sumright. Back to 1.

If all elements were consumed, there is no solution.

Edit: Testing if requirement is fulfilled when sumleft == sumright can be done by initially summing up all elements (also needs only O(n)) and checking if this sum minus the elements to drop is equal sumleft * 3.

15
  • Did you actually understand his question? Because I didn't. Can you explain to me what the "three parts " he is referring to means? All I understood was that he has an array that is somehow divided into three parts (he doesn't explain how the division happens or based on what). Oct 2, 2018 at 1:46
  • 4
    @AliElgazar If I understand right, two elements of the array are dropped and the places where they were dropped function then as separators to cut the array into three smaller subarrays (with equal sum of the elements). Oct 2, 2018 at 1:49
  • Hats off to you sir, I didn't understand that at all from his post. Well done. Oct 2, 2018 at 1:51
  • @MichaelButscher how would we get the third element this way?
    – Danish
    Aug 8, 2019 at 10:15
  • 1
    @Danish, what do you mean, which third element? Aug 8, 2019 at 16:16
0

The results below are more a "brute" approach, should work for negative numbers as well. Also a version where we can remove any 2 items and split by any index is added. although it's just a pseudo code.

if the array is split by those items we take out...

var count = a.Length (a is input)

// we need:
for i=0; i<cnt; i++
sum += a[i]
sumLeft[i] = a[i]; if (i > 0) sumLeft[i] += sumleft[i-1]
sumRight[cnt-1-i] = a[i]; if (i > 0) sumRight[cnt-1-i] += sumRight[cnt-1+1-i]

// calc:
for i=1; i<cnt; i++;
for j=cnt-2; j>i; j--;
if (sumLeft[i-1] == sumRight[j+1-1] == sum - a[i] - a[j] - sumLeft[i-1] - sumRight[j-1]) return true;

otherwise return false aft cycle

if we can take out any 2 items and split in any position:

for i=0; i<cnt; i++
for j=i+1; j<cnt; j++
newSum = sum - a[i] - a[j]
if (newSum mod 3 != 0) continue;
if passes check(newSum, i, j, a), return true

return false aft cycle

the check (newSum, dropi, dropj, a):
  thirdSum = newSum / 3

  // summarize from left, until we get the third'sum - if we exceed it, we don't have a result
  leftSum = 0;
  i=0;
  do {
    if (i != dropi && i !- dropj) leftSum += a[i]
    i++;
  } while leftSum < thirdSum
  if (thirdSum != leftSum) return false;

  right = 0;
  i=a.Length-1;
  do {
    if (i != dropi && i !- dropj) rightSum += a[i]
    i++;
  } while rightSum < thirdSum
  if (thirdSum != rightSum) return false;

  return true;

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.