Split Array With Same Average

HARD

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.

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] <= 10⁴

Approaches

Checkout 2 different approaches to solve Split Array With Same Average. Click on different approaches to view the approach and algorithm in detail.

Brute-force Backtracking

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.

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 Analysis

Time Complexity: 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 Complexity: O(N), where N is the number of elements in `nums`. This is for the recursion stack depth.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Split Array With Same Average. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Split Array With Same Average

Patterns:

MathDynamic ProgrammingBit ManipulationBitmask

Data Structures:

Array