Split Array With Equal Sums

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
8 upvotes
Asked in companies
alibabaD.E.ShawCapegemini Consulting India Private Limited

Problem statement

You are given an array/list 'ARR' of size 'N'. You task is to find if there exists a triplet (i, j, k) such that 0 < i , i + 1 < j , j + 1 < k and k < 'N' - 1 and the sum of the subarrays [0, i - 1],[i + 1, j - 1], [j + 1, k - 1], [k + 1, N - 1] are equal.

An array c is a subarray of array d if c can be obtained from d by deletion of several elements from the beginning and several elements from the end.

Example:

let 'ARR' = [1, 2, 3] then the possible subarrays of 'ARR' will be - {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}.
Note: Assume That the Array has Zero-based indexing.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains an integer  ‘N’ representing the array’s size.

The second line of each test case contains 'N' space-separated integers representing the array’s elements.
Output format: 
For each test case, print ‘True’ if such a triplet exists; else print ‘False’.

Output for each test case will be printed in a separate line.

Note:

You don’t have to take any input or print anything; it already has been taken care of. Just implement the function.
Constraints: 
1 <= T <= 5
1 <= N <= 10 ^ 3
-10 ^ 6 <= ARR[i] <= 10 ^ 6

Time Limit: 1 sec
Sample Input 1:
2
7
1 2 1 2 1 2 1 
5
1 2 3 1 2
Sample Output 1:
True
False
Explanation For Sample Input 1:
In first test case, If we take i = 1, j = 3 and k =5 we get - sum[0,i-1]  -> sum[0,0]=1, sum[i+1, j-1] -> sum[2,2]=1, sum[j+1, k-1] -> sum[4,4]=1, sum[k+1,N-1] -> sum[6,6]=1. Here the sum of all subarrays formed is 1, So, "True" will be printed.

In second test case, here N = 5, the first condition i.e 0 < i, i - 1< j, j - 1 < k, k - 1 < n doesn’t satisfy for any triplet. So "False" will be printed.
Sample Input 2:
2
6
1 2 1 2 1 2
9
1 2 3 -5 8 1 3 2 3
Sample Output 2:
False
True
Explanation For Sample Input 2:
In first test case, we cannot get any triplet as equal sum is not possible. So, "False" is printed.

In second test case, we can get any triplet as equal sum is possible which is 3 by taking i = 2, j = 5 and j = 7. So, "True" is printed.
Hint

Think this by traversing over every subarray of the given array and checking whether these cuts we are making out of our indices i, j, k  satisfy the given conditions.

Approaches (3)
Brute Force

To implement this approach, You have to understand the constraints first, i.e., 0 < i, i+1 < j , j+1< k < N-1.

If you carefully look at the constraints, you may notice the problem while splitting the array into slices or subarrays does not include the elements at index i,  j, and k. So it can be simply observed that according to constraints during the slices you make, three of the elements will not get included in any of the slices. Every Slice needs to be non-empty, too, so your task is to make four of these partitions. You can conclude from these points that the array size should be at least 7 to find such a triplet, any size below 7 will result in ‘False’.

 

To simplify this we can write this as:

0 < i < N - 5 

i + 1 < j < N - 3

j + 1 < k < N - 1

 

The algorithm will be:

 

  1. We can iterate over each ‘i’ from 1 to ‘N’ - 5:
    • Now for each ‘j’ from ‘i’ + 1 to ‘N’ - 3:
      • Now for each 'k' from 'j' + 1 to 'N' - 1:
        • We can calculate the sum for each of the above-formed subarray in one iteration.
        • If the sum of the subarrays is equal we return ‘True’.
  2. If we do not find any valid triplet we return ‘False’.
Time Complexity

O(N^4), where N is the size of ARR.

 

We are iterating over all possible i, j and k in O(N^3) time complexity. For each possible i, j and k we are finding the sum of the subarray in O(N) time complexity. Hence overall time complexity will be O(N^4).

Space Complexity

O(1)

 

Because, Constant space is used.

Code Solution
(100% EXP penalty)
Split Array With Equal Sums
Full screen
Console