We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Split Array With Same Average

Difficulty: Hard

Problem Description

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.

Key Insights

  • The average of two arrays is equal if the sum of the elements of each array divided by their respective sizes is the same.
  • A necessary condition for splitting is that the total sum of the elements must be divisible by the total number of elements.
  • We need to explore all possible combinations of splitting the array using subsets, which can be efficiently handled using dynamic programming or bit manipulation.
  • The maximum number of elements we can select for one of the arrays is up to half of the total number of elements, due to symmetry.

Space and Time Complexity

Time Complexity: O(n * sum), where n is the number of elements and sum is the total sum of elements. Space Complexity: O(n * sum), for storing states in the dynamic programming approach.

Solution

To solve the problem, we can use a dynamic programming approach to determine if there exists a non-empty subset of the array that can achieve a specific sum that would allow for equal averages. The key steps are as follows:

  1. Calculate the total sum and length of the input array.
  2. For each possible size of the subset (from 1 to n-1), check if there exists a subset of that size with a sum that can be derived from the averages being equal.
  3. Use a boolean DP array to keep track of achievable sums for different sizes of subsets.

Code Solutions

def splitArraySameAverage(nums):
    n = len(nums)
    total_sum = sum(nums)
    
    # Create a DP array where dp[i][j] indicates if there's a subset of size i with sum j
    dp = [set() for _ in range(n + 1)]
    dp[0].add(0)  # Base case: sum of 0 with 0 elements

    for num in nums:
        for i in range(n, 0, -1):
            for s in dp[i - 1]:
                dp[i].add(s + num)

    for size in range(1, n):
        if total_sum * size % n == 0:
            target_sum = total_sum * size // n
            if target_sum in dp[size]:
                return True
    return False
← Back to All Questions