Count the number of ways to divide an array into three contiguous parts having equal sum
Given a array of n numbers. Our task is to find out the number of ways to divide the array into three contiguous parts such that the sum of three parts is equal. In other words, we need to find the number of index pairs i and j such that sum of elements from 0 to i1 is equal to sum of elements from i to j is equal to the sum of elements from j+1 to n1.
Examples:
Input : arr[] = {1, 2, 3, 0, 3} Output : 2 Following are two possible ways to partition 1) Three parts are (0, 1), (2, 2) and (3, 4) 2) Three parts are (0, 1), (2, 3) and (4, 4) Input : arr[] = {0, 1, 1, 0} Output : 1
If the sum of all the elements of array is not divisible by 3 return 0. Else it is obvious that the sum of each part of each contiguous part will be equal to sum of all elements divided by 3.
Step 1 : Create an array of same size as given array whose ith index holds the value of sum of elements from indices 0 to i of the given array. Let’s call it prefix array
Step 2 : Create another array of same size as given array whose ith index the value of sum of elements from indices i to n1 of the given array. Let’s call it suffix array.
Step 3 : The idea is simple, we start traversing the prefix array and suppose at the ith index of the prefix array the value of prefix array is equal to (sum of all elements of given array)/3.
Step 4 : For the i found in the above step we look into the suffix array from (i+2)th index and wherever the value of suffix array is equal to (sum of all elements of given array)/3, we increase the counter variable by 1.
To implement step 4 we traverse suffix array and wherever the value of suffix array is equal to the sum of all elements of given array/3 we push that index of suffix array into the vector. And we do binary search in the vector to calculate number of values in suffix array which are as according to the step 4.
We search in suffix array because there should be at least 1 element between the first and third part.
For more explanation see implementation below

// C++ program to count number of ways we can
// partition an array in three parts with equal
// sum.
#include<bits/stdc++.h>
using
namespace
std;
// binary search to find the number of required
// indices in suffix array. Returns index of
// first element which is greater than x.
int
binarysearch(vector <
int
> &v,
int
x)
{
int
low = 0, high = v.size()1;
while
(low <= high)
{
int
mid = (low + high)/2;
if
(v[mid] <= x)
low = mid + 1;
else
if
(v[mid] > x && v[mid1] <= x)
return
mid;
else
if
(v[mid] > x && mid == 0)
return
mid;
else
high = mid1;
}
return
1;
}
// function to calculate the number of ways to
// divide the array into three contiguous parts
int
CountContiguousParts(
int
arr[] ,
int
n)
{
int
count = 0;
// initialising answer
// Creating and filling prefix array
int
prefix[n];
prefix[0] = arr[0];
for
(
int
i=1; i<n; i++)
prefix[i] = prefix[i1] + arr[i];
// Total sum of elements is equal to last
// value in prefix array.
int
total_sum = prefix[n1];
// If sum of all the elements is not dvisible
// by 3, we can't divide array in 3 parts of
// same sum.
if
(total_sum%3 != 0)
return
0;
// Crearing and filling suffix array
int
suffix[n];
suffix[n1] = arr[n1];
for
(
int
i=n2; i>=0; i)
suffix[i] = suffix[i+1] + arr[i];
// Storing all indexes with suffix
// sum equal to total sum by 3.
vector <
int
> v;
for
(
int
i=0; i<n; i++)
if
(suffix[i] == total_sum/3)
v.push_back(i);
// Traversing the prefix array and
// doing binary search in above vector
for
(
int
i=0; i<n; i++)
{
// We found a prefix with total_sum/3
if
(prefix[i] == total_sum/3)
{
// Find first index in v[] which
// is greater than i+1.
int
res = binarysearch(v, i+1);
if
(res != 1)
count += v.size()  res;
}
}
return
count;
}
// driver function
int
main()
{
int
arr[] = {1 , 2 , 3 , 0 , 3};
int
n =
sizeof
(arr)/
sizeof
(arr[0]);
cout << CountContiguousParts(arr, n);
return
0;
}
Output:
2
Time Complexity is O(n log n)
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide