Split Array With Same Average Solution in Python

Problem Description

So, you think you can just split an array into two parts and magically make their averages equal? Well, welcome to the real world, where math doesn’t always play nice! The problem at hand is to determine if you can split an array of integers into two non-empty subsets such that both subsets have the same average.

Imagine you have a group of friends who all want to share a pizza. You want to split the pizza into two groups, but you want to make sure that both groups get the same amount of pizza per person. If one group ends up with a slice of pizza that’s twice the size of what the other group gets, well, let’s just say that friendship might be tested!

Code Solution


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

Approach Explanation

The code provided uses a dynamic programming approach to solve the problem. It first checks if it’s even possible to split the array into two parts with the same average by ensuring that the total sum can be evenly divided by the number of elements. Then, it builds up possible sums for subsets of the array using a set to keep track of achievable sums. Finally, it checks if any of these sums correspond to the required average for valid splits.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n² * sum)
Space Complexity	O(n)

Real-World Example

Let’s say you have a group of friends who are planning a road trip. They decide to split the costs of gas and snacks. If one friend pays for gas and another pays for snacks, they want to ensure that the amount each person contributed is fair. If one person ends up paying significantly more than the others, it could lead to some awkward conversations. This problem is akin to ensuring that the contributions (or averages) are balanced among the group.