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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Split Array With Same Average

Number: 823

Difficulty: Hard

Paid? No

Companies: tcs, Microsoft

Problem Description

Given an integer array nums, determine if it is possible to partition the array into two non-empty subsets A and B such that the averages of A and B are equal.

Key Insights

  • Two sets have the same average if and only if for some subset size k (1 ≤ k ≤ n/2), the sum of its elements is exactly (total_sum * k) / n.
  • The problem reduces to a subset sum search on k elements.
  • Use dynamic programming to build sets of achievable sums for every possible count of selected numbers.
  • Early pruning is possible when no valid k exists such that (total_sum * k) is divisible by n.

Space and Time Complexity

Time Complexity: O(n * 2^n) in the worst case due to the subset sum exploration (n is relatively small, maximum 30). Space Complexity: O(n * possible_sums) where possible_sums depends on the range and combination of numbers, but is bounded by combinatorial growth for n up to 30.

Solution

We use a dynamic programming approach that tracks achievable sums for every possible subset size using an array dp where dp[k] is a set containing all possible sums that can be formed by selecting k elements from nums. First, we calculate the total sum (s) and the array length (n). It is necessary to check for each possible k in [1, n/2] if (s * k) % n equals 0; if not, no valid subset can have the required target sum. For each element in nums, iterate backwards through the dp array so that each new number is only used once. If a subset of size k exists that sums up to (s * k)/n, the answer is true.

Code Solutions

class Solution:
    def splitArraySameAverage(self, nums):
        n = len(nums)
        total_sum = sum(nums)
        # Early pruning: Check if any k (from 1 to n//2) can satisfy average condition
        possible = False
        for k in range(1, n // 2 + 1):
            if (total_sum * k) % n == 0:
                possible = True
                break
        if not possible:
            return False
        
        # dp[k] holds all sums achievable using k numbers
        dp = [set() for _ in range(n + 1)]
        dp[0].add(0)
        
        # Build up dp array: iterate over each number and update possible sums
        for num in nums:
            for k in range(n - 1, -1, -1):  # iterate in reverse to avoid reusing num
                for prev_sum in dp[k]:
                    dp[k + 1].add(prev_sum + num)
        
        # Check if for any k (1 <= k <= n//2) an appropriate sum exists
        for k in range(1, n // 2 + 1):
            if (total_sum * k) % n == 0:
                target = (total_sum * k) // n
                if target in dp[k]:
                    return True
        return False
← Back to All Questions