805. Split Array With Same Average LeetCode Solution
In this guide, you will get 805. Split Array With Same Average LeetCode Solution with the best time and space complexity. The solution to Split Array With Same Average problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 <= 30
0 <= nums[i] <= 104
Complexity Analysis
Time Complexity: O(2^{n / 2})
Space Complexity: O(2^{n / 2})
805. Split Array With Same Average LeetCode Solution in C++
class Solution {
public:
bool splitArraySameAverage(vector<int>& nums) {
const int n = nums.size();
const int sum = accumulate(nums.begin(), nums.end(), 0);
if (!isPossible(sum, n))
return false;
vector<unordered_set<int>> sums(n / 2 + 1);
sums[0].insert(0);
for (const int num : nums)
for (int i = n / 2; i > 0; --i)
for (const int val : sums[i - 1])
sums[i].insert(num + val);
for (int i = 1; i < n / 2 + 1; ++i)
if (i * sum % n == 0 && sums[i].contains(i * sum / n))
return true;
return false;
}
private:
bool isPossible(int sum, int n) {
for (int i = 1; i < n / 2 + 1; ++i)
if (i * sum % n == 0)
return true;
return false;
}
}; /* code provided by PROGIEZ */
805. Split Array With Same Average LeetCode Solution in Java
class Solution {
public boolean splitArraySameAverage(int[] nums) {
final int n = nums.length;
final int sum = Arrays.stream(nums).sum();
if (!isPossible(sum, n))
return false;
List<Set<Integer>> sums = new ArrayList<>();
for (int i = 0; i < n / 2 + 1; ++i)
sums.add(new HashSet<>());
sums.get(0).add(0);
for (final int num : nums)
for (int i = n / 2; i > 0; --i)
for (final int val : sums.get(i - 1))
sums.get(i).add(num + val);
for (int i = 1; i < n / 2 + 1; ++i)
if (i * sum % n == 0 && sums.get(i).contains(i * sum / n))
return true;
return false;
}
private boolean isPossible(int sum, int n) {
for (int i = 1; i < n / 2 + 1; ++i)
if (i * sum % n == 0)
return true;
return false;
}
} // code provided by PROGIEZ
805. Split Array With Same Average LeetCode Solution in Python
class Solution:
def splitArraySameAverage(self, nums: list[int]) -> bool:
n = len(nums)
summ = sum(nums)
if not any(i * summ % n == 0 for i in range(1, n // 2 + 1)):
return False
sums = [set() for _ in range(n // 2 + 1)]
sums[0].add(0)
for num in nums:
for i in range(n // 2, 0, -1):
for val in sums[i - 1]:
sums[i].add(num + val)
for i in range(1, n // 2 + 1):
if i * summ % n == 0 and i * summ // n in sums[i]:
return True
return False # code by PROGIEZ
