Number of Ways · Interview Problem

Back to problems

Codeforces

Medium

Arrays

Dynamic Programming

Math

Google

Number of Ways

Count how many ways to split an array into three contiguous parts with equal sum.

Acceptance 0%

Start Practice

Problem Statement

You are given an array of integers. Count the number of ways to choose two cut points so that the array is split into three non-empty contiguous parts, and the sum of each part is the same.

More formally, for an array $a$ of length $n$ , count pairs $(i, j)$ such that:

$1 \le i < j \le n-1$
the subarray $a[0..i-1]$ , $a[i..j-1]$ , and $a[j..n-1]$ all have the same sum

Return the number of valid splits.

Input Format

The first line contains an integer $n$ .
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ .

Output Format

Print a single integer: the number of valid ways to split the array into three non-empty contiguous parts with equal sum.

Constraints

$1 \le n \le 10^5$
Array values may be negative, zero, or positive.
The answer may be large; use a 64-bit integer.
In the original contest setting, the count is computed exactly without needing modulo unless specified by the platform statement.

Examples

Sample cases returned by the problem API.

Example 1

Input

5
1 2 3 0 3

Output

Explanation

The total sum is 9, so each part must sum to 3. The valid splits are [1,2] | [3] | [0,3] and [1,2] | [3,0] | [3].

Example 2

Input

4
0 0 0 0

Output

Explanation

Every part must sum to 0. The valid cut pairs are any two distinct cut points among the 3 available positions, so the number of ways is 3.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress