# 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;
}
}
}

}
``````

}

#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.