##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/805.html

# 805. Split Array With Same Average (Hard)

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input:
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.


Note:

• The length of A will be in the range [1, 30].
• A[i] will be in the range of [0, 10000].

Related Topics:
Math

## Solution 1. Brute Force

Our goal is to find a non-empty subsequence B which satisfies Sum(B) * N == Sum(A) * Len(B), where N is the length of A.

We can try to get all the sums of the subsequences of A. There are 2^N subsequences of A.

We can’t put all the sums of subsequences into a single set since the length of the subsequence matters.

So we store the sums of subsequences into vector<unordered_set<int>> v(N + 1), where v[i] is a set of sums of subsequences of length i and v[0] = {0}.

We try using each A[i] to update v. For each value n in v[j], we put n + A[i] into v[j + 1].

If any (n + A[i]) * N == Sum(A) * (j + 1), we can return true.

// OJ: https://leetcode.com/problems/split-array-with-same-average/
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int N = A.size(), sum = accumulate(A.begin(), A.end(), 0);
vector<unordered_set<int>> v(N + 1);
v[0] = {0};
for (int i = 0; i < N; ++i) {
for (int j = i; j >= 0; --j) {
if (j == N - 1) continue;
for (int n : v[j]) {
int m = n + A[i];
if (m * N == sum * (j + 1)) return true;
v[j + 1].insert(m);
}
}
}
return false;
}
};


## Solution 2.

// OJ: https://leetcode.com/problems/split-array-with-same-average/
// Time: O(n^3 * M) where M the maximum possible number in A
// Space: O(n^2 * M)
// Ref: https://leetcode.com/problems/split-array-with-same-average/discuss/120667/C%2B%2B-Solution-with-explanation-early-termination-(Updated-for-new-test-case)
class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int N = A.size(), sum = accumulate(A.begin(), A.end(), 0), M = N / 2;
bool possible = false;
for (int i = 1; i <= N && !possible; ++i) possible = sum * i % N == 0;
if (!possible) return false;
vector<unordered_set<int>> v(M + 1);
v[0] = {0};
for (int i = 0; i < N; ++i) {
for (int j = min(M, i + 1); j >= 1; --j) {
for (int n : v[j - 1]) {
int m = n + A[i];
if (m * N == sum * j) return true;
v[j].insert(m);
}
}
}
return false;
}
};

• class Solution {
public boolean splitArraySameAverage(int[] A) {
if (A == null || A.length < 2)
return false;
Arrays.sort(A);
int length = A.length;
if (A[length - 1] == 0)
return true;
int gcd = A[length - 1];
for (int i = length - 2; i >= 0; i--) {
if (A[i] == 0)
break;
gcd = gcd(gcd, A[i]);
}
for (int i = length - 1; i >= 0; i--) {
if (A[i] == 0)
break;
A[i] /= gcd;
}
int sum = 0;
for (int num : A)
sum += num;
if (gcd(sum, length) == 1)
return false;
if (A[length - 2] * (length - 1) < sum - A[length - 2])
return false;
int power = 1 << length;
for (int i = 1; i < power - 1; i++) {
int curCount = 0;
int curSum = 0;
for (int j = length - 1; j >= 0; j--) {
if ((i >> j & 1) != 0) {
curCount++;
curSum += A[j];
}
}
if (sum * curCount == curSum * length)
return true;
}
return false;
}

public int gcd(int num1, int num2) {
if (num1 == 0 && num2 == 0)
return 1;
else if (num1 == 0)
return num2;
else if (num2 == 0)
return num1;
else {
while (num1 != 0 && num2 != 0) {
if (num1 > num2) {
int temp = num1;
num1 = num2;
num2 = temp;
}
num2 %= num1;
}
return num1 == 0 ? num2 : num1;
}
}
}

############

class Solution {
public boolean splitArraySameAverage(int[] nums) {
int n = nums.length;
if (n == 1) {
return false;
}
int s = Arrays.stream(nums).sum();
for (int i = 0; i < n; ++i) {
nums[i] = nums[i] * n - s;
}
int m = n >> 1;
Set<Integer> vis = new HashSet<>();
for (int i = 1; i < 1 << m; ++i) {
int t = 0;
for (int j = 0; j < m; ++j) {
if (((i >> j) & 1) == 1) {
t += nums[j];
}
}
if (t == 0) {
return true;
}
}
for (int i = 1; i < 1 << (n - m); ++i) {
int t = 0;
for (int j = 0; j < (n - m); ++j) {
if (((i >> j) & 1) == 1) {
t += nums[m + j];
}
}
if (t == 0 || (i != (1 << (n - m)) - 1) && vis.contains(-t)) {
return true;
}
}
return false;
}
}

• // OJ: https://leetcode.com/problems/split-array-with-same-average/
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int N = A.size(), sum = accumulate(A.begin(), A.end(), 0);
vector<unordered_set<int>> v(N + 1);
v[0] = {0};
for (int i = 0; i < N; ++i) {
for (int j = i; j >= 0; --j) {
if (j == N - 1) continue;
for (int n : v[j]) {
int m = n + A[i];
if (m * N == sum * (j + 1)) return true;
v[j + 1].insert(m);
}
}
}
return false;
}
};

• class Solution:
def splitArraySameAverage(self, nums: List[int]) -> bool:
n = len(nums)
if n == 1:
return False
s = sum(nums)
for i, v in enumerate(nums):
nums[i] = v * n - s
m = n >> 1
vis = set()
for i in range(1, 1 << m):
t = sum(v for j, v in enumerate(nums[:m]) if i >> j & 1)
if t == 0:
return True
for i in range(1, 1 << (n - m)):
t = sum(v for j, v in enumerate(nums[m:]) if i >> j & 1)
if t == 0 or (i != (1 << (n - m)) - 1 and -t in vis):
return True
return False


• func splitArraySameAverage(nums []int) bool {
n := len(nums)
if n == 1 {
return false
}
s := 0
for _, v := range nums {
s += v
}
for i, v := range nums {
nums[i] = v*n - s
}
m := n >> 1
vis := map[int]bool{}
for i := 1; i < 1<<m; i++ {
t := 0
for j, v := range nums[:m] {
if (i >> j & 1) == 1 {
t += v
}
}
if t == 0 {
return true
}
vis[t] = true
}
for i := 1; i < 1<<(n-m); i++ {
t := 0
for j, v := range nums[m:] {
if (i >> j & 1) == 1 {
t += v
}
}
if t == 0 || (i != (1<<(n-m))-1 && vis[-t]) {
return true
}
}
return false
}