[NDA] Fortune 500 Company - OA - Bay Area [5+ yoe] - Sr. SW Engineer
Anonymous User
67

Given an array A, find the number of ways to split the array into three subarrays A1, A2, A3 such that their sums are S1, S2, S3 and S2 <= S1 + S3. Subarray can only have contiguous elements. Each subarray must have atleast 1 element. If no such split is possible, return 0.

Example - 1:
A = [1,2,3,4]
Output: 2
Details: A can be broken down into 3 subarrays as follows:
- Option 1: A1 = [1], A2 = [2,3], A3 = [4]. Here S1 = 1, S2 = 5, S3 = 4 --> Hence S2 <= S1 + S3
- Option 2: A1 = [1,2], A2 = [3], A3 = [4]. Here S1 = 3, S2 = 3, S3 = 4 --> Hence S2 <= S1 + S3

Example - 2:
A = [4,20,5]
Output: 0
Details: Not possible to split A into three subarrays as per given requirement

Comments (0)