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
Awill 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; } vis.add(t); } 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 vis.add(t) 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 }