Scale Engineer

Split Array With Same Average

Hard
#0759Time: O(N * 2^N). The recursive function `canFindSum` explores `2^N` paths in the worst case. This function is called in a loop that runs up to `N/2` times.Space: O(N), where N is the number of elements in `nums`. This is for the recursion stack depth.
Patterns
MathDynamic ProgrammingBit ManipulationBitmask
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This is a straightforward approach that checks every possible partition of the array. We can use recursion to generate all subsets of nums to form the first array A. For each generated subset A, we check if it's a valid candidate (non-empty and not the full array). If it is, we calculate its average and the average of the remaining elements (forming array B). If the averages are equal, we've found a solution.

Algorithm

  • The core idea is to check for each possible subset A if avg(A) == avg(nums). The condition avg(A) == avg(B) simplifies to avg(A) == avg(nums).
  • This can be written as sum(A) / len(A) == totalSum / N, or sum(A) * N == totalSum * len(A).
  • We can iterate through all possible lengths k for subset A from 1 to N-1.
  • For each k, we need to find if there's a subset of size k with a sum equal to (totalSum * k) / N.
  • A recursive helper function find(index, k, targetSum) can be used to solve this subset sum problem.
  • The function explores two paths at each element nums[index]: either include it in the subset or not.
  • The recursion stops when a subset of size k is formed or when all elements are processed.

Walkthrough

The problem asks if we can partition nums into two non-empty arrays A and B with equal averages. This condition sum(A)/len(A) == sum(B)/len(B) is equivalent to sum(A)/len(A) == totalSum/N, where totalSum and N are the sum and length of the original array nums. This simplifies to sum(A) * N == totalSum * len(A).

This transforms the problem into a search for a non-empty proper subset A that satisfies this equation. The brute-force approach is to generate all possible subsets of nums, and for each subset, check if it satisfies the condition. We can implement this using a backtracking algorithm. We iterate through all possible lengths k for the subset A (from 1 to N/2) and for each k, we check if a subset of this size exists with the required sum (totalSum * k) / N. The check is done via a recursive function that explores including or excluding each element from the subset.

class Solution {    public boolean splitArraySameAverage(int[] nums) {        int n = nums.length;        if (n < 2) {            return false;        }        int totalSum = 0;        for (int num : nums) {            totalSum += num;        }         for (int k = 1; k <= n / 2; k++) {            if ((totalSum * k) % n == 0) {                int targetSum = (totalSum * k) / n;                if (canFindSum(nums, 0, k, targetSum)) {                    return true;                }            }        }        return false;    }     private boolean canFindSum(int[] nums, int index, int k, int targetSum) {        if (k == 0) {            return targetSum == 0;        }        if (index >= nums.length || k < 0 || targetSum < 0) {            return false;        }         // Option 1: Include nums[index] in the subset        if (canFindSum(nums, index + 1, k - 1, targetSum - nums[index])) {            return true;        }         // Option 2: Exclude nums[index] from the subset        if (canFindSum(nums, index + 1, k, targetSum)) {            return true;        }         return false;    }}

Complexity

Time

O(N * 2^N). The recursive function `canFindSum` explores `2^N` paths in the worst case. This function is called in a loop that runs up to `N/2` times.

Space

O(N), where N is the number of elements in `nums`. This is for the recursion stack depth.

Trade-offs

Pros

  • Simple to understand and implement.

  • It's a good starting point for thinking about the problem.

Cons

  • Highly inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.

Solutions

class Solution {public  boolean splitArraySameAverage(int[] nums) {    int n = nums.length;    if (n == 1) {      return false;    }    int s = Arrays.stream(nums).sum();    for (int i = 0; i < n; ++i) {      nums[i] = nums[i] * n - s;    }    int m = n >> 1;    Set<Integer> vis = new HashSet<>();    for (int i = 1; i < 1 << m; ++i) {      int t = 0;      for (int j = 0; j < m; ++j) {        if (((i >> j) & 1) == 1) {          t += nums[j];        }      }      if (t == 0) {        return true;      }      vis.add(t);    }    for (int i = 1; i < 1 << (n - m); ++i) {      int t = 0;      for (int j = 0; j < (n - m); ++j) {        if (((i >> j) & 1) == 1) {          t += nums[m + j];        }      }      if (t == 0 || (i != (1 << (n - m)) - 1) && vis.contains(-t)) {        return true;      }    }    return false;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem