Question

Given an array A of size N, and a number K. Task is to find out if it is possible to partition the array A into K contiguous subarrays such that the sum of elements within each of these subarrays is the same.Prerequisite : Count the number of ways to divide an array into three contiguous parts having equal sum

Answer 1

Answer: First lets solve the Prerequisite part

Lets say we have an input array of N numbers {3,2,5,0,5}. We have to  find number of ways to divide this array into 3 contiguous parts having equal sum. So the output for the above input array will be 2 as there are 2 ways to divide the array. One is (3,2),(5),(0,5) and the other is (3,2),(5,0),(5).

Following are the steps to achieve the above outcome.

• Let p and q point to the index of array such that sum of array elements from 0 to p-1 is equal to sum of array elements from p to q which is equal to the sum of array elements from q+1 to N-1.  
• If we see the array we can tell that the sum of 3 contiguous parts is 5. So the condition would be that sum of all array elements should be equal to 5 or sum of each contiguous part is equal to sum of all array elements divided by 5.
• Now create 2 arrays prefix and postfix of size of input array. Index p of prefix array carries sum of input array elements from index 0 to index p. Index q of postfix array carries sum of input array elements from index p to index N-1
• Next move through prefix array suppose at the index p of prefix array : value of prefix array == (sum of all input array elements)/5.
• Search the postfix array for p index found above. Search it starting from p+2 index. Increment the count variable by 1 when the value of postfix array =(sum of all input array elements)/5 and push that index of postfix array into a new array. Use searching algorithm on new array to calculate number of values in postfix array.

Now lets solve the main task

We have an array A of size N and a number K. where A[]= {1,6,3,4,7} N=5 and K=3. We have to find if its possible to partition A into 3 contiguous subarrays such that sum of elements in each subarray is the same. It is possible in this example. Here we have 3 partitions (1,6),(3,4),(7) and sum of each of subarrays is same (1+6) (3+4) (7) which is 7.

Following are the steps to achieve the above outcome.

• In order create K contiguous subarrays where each subarray has equal sum, first check the condition that sum of all elements in the given array should be divisible by K. Lets name another array as arrsum that will be the size of array A. Traverse A from first to  last index and keep adding current element of A with previous value in arrsum. Example A contains (1,6,3,4,7} and arrsum has {1,7,10,14,21}
• If the above condition holds, now check the condition that each subarray or partition has equal sum. Suppose we represent sum1 to sum of all element in given array and sum2 of sum of each partition then: sum2 = sum2 / K.
• Compare arrsum to subarray, begining from index 0 and when it becomes equal to sum2 this means that end of one subarray is reached. Lets say index q is pointing to that subarray.
• Now from q+1 index find p index in which following condition holds: (arrsum[p] - arrsum[q])=sum2
• Continue the above step untill K contigous subarrays are found. This loop will break if, at some index, sum2 of any subarray gets greater than required sum2 (as we know that every contiguous subarray should contain equal sum).

A easier function Partition for this task:

int Partition(int A[], int N, int k) // A arra y of size N and number k

{      int sum = 0;    int count = 0;  //variables initialization    

   for(int j = 0; j < N; j++)  //Loop that calculates sum of A

  sum = sum + A[j];        

  if(sum % k != 0) //checks condition that sum of all elements of A should be //divisible by k

   return 0;        

   sum = sum / k;  

   int sum2 = 0;  //represents sum of subarray

  for(int j = 0; j < N; j++) // Loop on subarrays

  {      sum2=sum2 + A[j];  

   if(sum2 == sum)    { //these lines locates subarrays and sum of elements //of subarrays should be equal

       sum2 = 0;  

       count++;  }  }  

/*calculate count of subarrays whose

sum is equal to (sum of complete array/ k.)

if count == k print Yes else print No*/

if(count == k)    

return 1;  

   else

   return 0;  }