Can any explain me the solution?


#1

Hi , I have gone through the solution but i am unable to draw any intuition how things are working under the hood. Even i have read the solution provided on GFG , but there also they are making prefix/suffix array which is basically cumulative sum array , but how that thing is helping in reaching to the desired solution ??

Please help me with the explaining the solution in detail. I have understood that sum of the array should be the multiple of 3 and each partition should be of sum/3 . but what is happening after that ??


#2

I will explain you how I worked up my solution. Lets get basic case right first. Sum of the given array must be a multiple of 3 for any chance of it having 3 partitions.
Next we create a suffix array, which will have a note of position where the sum is (sum/3) from the end.
Therefore when we iterate from front, (keeping sum count) as soon as we reach (sum/3) let say at i, we have probably got our 1st part(still there can be a chance that 3 partitions won’t exist). Now as we are looking for 3 parts, the 3rd part will start from i+2 or thereafter (2nd part can be at i+1). Therefore from i+2 position we check on our suffix array for instances where we tagged positions as 1. In all the places we find that, we have a successful case of 3 partition and we increase a totalCount by 1. Then we resume from out i th index and do the same again when the sum is (sum/3).

int Solution::solve(int A, vector &B) {

int sum = 0;
 for (int i = 0; i < A; i++){
    sum=sum+B[i];   
 }
 
 if(sum%3!=0){
     return 0;
 }
 int oneThird = sum/3;
 vector<int> temp(A,0);
 
 int tempSum=0;
 for(int i=A-1;i>=0;i--){
     tempSum += B[i];
     if(tempSum==oneThird){
         temp[i]=1;
     }
 }
 
 tempSum=0;
 int total=0;
 for(int i=0; i <A; i++){
     tempSum += B[i];
     if(tempSum == oneThird){
         for(int j=i+2;j<A;j++){
             if(temp[j]==1){
                 total+=1;
             }
         }
     }
     
 }
 return total;

}


#3

can anyone explain why we are only leaving one index ie ( doing i+2 )after getting the first division where sum of array is sum/3 ?? what if that no. is i+1 is not sum/3 ??


#4

Good Explanatory video

#5

The solution confused me too, until I realized that the only way there can be more than 1 way of partitioning the array is if the arrays contains negative numbers, so the sum decreases and increases again. I was able to meet the time constraint with an O(n^2) solution just by bailing out of the loop iterations as soon as one of the partition sums wasn’t equal to 1/3 to total sum, but their solution is more efficient.