Algorithm
Problem Name: 805. Split Array With Same Average
You are given an integer array nums.
You should move each element of nums into one of the two arrays A and B such that A and B are non-empty, and average(A) == average(B).
Return true if it is possible to achieve that and false otherwise.
Note that for an array arr, average(arr) is the sum of all the elements of arr over the length of arr.
Example 1:
Input: nums = [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 an average of 4.5.
Example 2:
Input: nums = [3,1] Output: false
Constraints:
1 <= nums.length <= 300 <= nums[i] <= 104
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
start coding...
class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int sum = 0, n = A.size();
for (int& x: A) {
sum += x;
}
sort(A.rbegin(), A.rend());
for (int i = 1; i < = n/2; ++i) {
if (sum*i%n == 0 && dfs(A, 0, i, sum*i/n, n)) {
return true;
}
}
return false;
}
bool dfs(vector<int>& A, int pos, int count, int target, int& n) {
if (count == 0) {
return target == 0;
}
if (pos == n || target > A[pos] * count) {
return false;
}
for (int i = pos; i < n; ++i) {
if (target >= A[i] && dfs(A, i + 1, count - 1, target - A[i], n)) {
return true;
}
}
return false;
}
};
Input
nums = [1,2,3,4,5,6,7,8]
Output
true
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const splitArraySameAverage = function(A) {
const totalSum = A.reduce((ac, el) => ac + el, 0)
const len = A.length
const mid = Math.floor(len / 2)
A.sort((a, b) => b - a)
for (let i = 1; i < = mid; i++) {
if ((totalSum * i) % len === 0 && combinationSum(A, 0, i, (totalSum * i) / len)) return true
}
return false
}
function combinationSum(nums, idx, k, target) {
if (target > k * nums[idx]) return false
if (k === 0) return target === 0
for (let i = idx; i < nums.length - k; i++) {
if (nums[i] <= target && combinationSum(nums, i + 1, k - 1, target - nums[i])) return true
}
return false
}
Input
nums = [1,2,3,4,5,6,7,8]
Output
true
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def splitArraySameAverage(self, A):
def find(target, k, i):
if (target,k) in not_found and not_found[(target,k)] <= i: return False
if k == 0: return target == 0
if k + i > len(A): return False
res = find(target - A[i], k - 1, i + 1) or find(target, k, i + 1)
if not res: not_found[(target, k)] = min(not_found.get((target, k), n), i)
return res
not_found = dict()
n, s = len(A), sum(A)
return any(find(s * i / n, i, 0) for i in range(1, n // 2 + 1) if s * i % n == 0)
Input
nums = [3,1]
Output
false