Did not understand the logic, can someone help


#1
int Solution::solve(int A, vector<int> &B) {
  int s[100005];
  s[0] = 0;
  A=B.size();
  for (int i = 0; i < B.size(); i++) 
   {
    s[i + 1] = s[i] + B[i];                           // Make a prefix array for getting sum in O(1)
   }
  long long int ans = 0;
  if(s[A] % 3 == 0)                                   // It is possible to make 3 partition only if array sum is multiple of 3
   {
  >   long long int u = s[A] / 3, v = 2 * s[A] / 3;     
>     long long int cnt = 0;                            // Count for first partition
>     for (int i = 1; i < A; i++) 
>      {
>       if (s[i] == v)
>        {
>         ans += cnt;                                   // If sum is of 2 partitions then add the count to answer
>        }
>        
>       if (s[i] == u)
>        {
>         cnt++;                                        // If sum is of 1 partition then increase the count by 1
>        }
>      }
   }
  return ans;
}

#2

I can explain the code with the help of example given.
Hope it helps.
First of all find the prefix sum as it will help later to detect whether partition with given sum occurs or not.
Also the last value of prefix array will provide us with the total sum of array.
Now, since we have to divide the array into 3 contiguous subarrays having equal sum, it is clear that the sum of the individual subarrays will be (total sum of the array) / 3. Also, if total sum of array is not divisible by 3 then answer will be zero.
Now we have the sum of individual subarrays with us and also v = 2* (s[A] / 3)is just the sum of 2 partitions.
Notice that answer is updated when we have prefix sum which is equal to v and the count is updated when we encounter a prefix sum of u which is s[A] / 3. Now why this thing?
This is because:
Consider this example:
1, 2, 3, 0, 3
Prefix array:
1, 3, 6, 6, 9
Here, u = 9 / 3 = 3 and v = 3*2 = 6.
Coming to the above point: if you didn’t encounter 3 but directly encounter 6 in the prefix array, the answer will be 0 only as it implies that no partition till that point is there with sum exactly equal to 3.
Consider the below example for better explaination:
Array: 1, 1, 4, 0, 3
Prefix array: 1, 2, 6, 6, 9
Here u and v are same . But since we don’t have any partition with sum 3 hence even after having sum = 6 answer will be zero.

Hope, it clears your doubt.Also, correct me if I seem to be wrong at some point.


#3

Good explanation Pranjali.


#4

still, I didn’t understand the thing that answer is updated when we have prefix sum which is equal to v, and the count is updated when we encounter a prefix sum of u which is s[A] / 3.


#5

We have already checked that sum of array is divisible by 3. Now if we found that one sum in prefix array (u) as 1/3rd of total sum(i.e, 3 in above case) and v as 2/3rd it is clear that the remaining part will add up to the total sum that is remaining 1/3rd part of sum.So we just have to find out 2/3rd of total sum after getting 1/3rd. This part is explained by pranjali pretty well.
Hope this clarifies what u asked.