43. Split Array With Equal Averages

Difficulty: easy · Array, Prefix Sum, Math

Problem

Given an array of `n` integers, decide whether it can be cut at one point into two non-empty parts (a prefix `arr[0..k-1]` and the remaining suffix `arr[k..n-1]`, with `1 <= k <= n-1`) whose averages are exactly equal. Print `true` if such a cut exists, otherwise `false`.

Input

- Line 1: the integer `n`. - Line 2: `n` space-separated integers.

Output

Print `true` or `false`.

Example 1

Input:
4
1 3 2 2
Output:
true

Explanation: Cutting after the 2nd element gives [1, 3] and [2, 2], both with average 2.

Example 2

Input:
3
1 2 4
Output:
false

Explanation: Cuts give averages 1 vs 3 and 1.5 vs 4; neither matches.

Constraints

- 1 <= n <= 10^5 - -10^4 <= arr[i] <= 10^4

Solutions are judged against 2 sample and 9 hidden tests. Sign in to solve it · All problems