hard Split Array With Same Average

Problem Statement

You are given an array of integers nums.

You should insert each element of nums in either array A or B such that A and B are non-empty, and average(A) == average(B).

The average of arr is the sum of all the elements of arr divided by the length of arr.

Return true if it is possible to divide nums into two subarrays having the same average. Otherwise, return false.

Examples

1. Example 1:

   • Input: nums = [1, 5, 3, 5, 6]
   • Expected Output: true
   • Explanation: We can split the array into A = [1, 5, 6] and B = [3, 5]. The average of both subarrays is 4.

2. Example 2:

   • Input: nums = [3, 5, 6, 4, 2, 10]
   • Expected Output: true
   • Explanation: We can split the array into A = [6, 4] and B = [3, 5, 2, 10]. The average of both subarrays is 4.

3. Example 3:

   • Input: nums = [4, 8, 16, 24, 32, 40]
   • Expected Output: false
   • Explanation: It's not possible to split the array into two subarrays with the same average.

Constraints:

• 1 <= nums.length <= 30
• 0 <= nums[i] <= 10 ⁴

Solution

To solve this problem, we approach it by dividing the array into two halves and then generating all possible subsets for each half. This allows us to explore different ways to split the array into two non-empty subsets. The goal is to find two subsets, one from each half, such that the average of the elements in the two subsets is the same. To do this, we calculate the sum for each subset and use a mathematical relationship to determine if a corresponding subset exists in the other half. We leverage the fact that if the average of two subsets is the same, the equation involving their sums and sizes must hold true.

The algorithm first computes all possible subset sums for each half of the array. Then, it sorts the subset sums for one half to allow efficient searching using binary search. For each subset in the first half, the algorithm calculates the sum required in the second half to maintain the average equality. If such a sum exists in the sorted subset sums of the second half, the algorithm returns true. If no valid pair of subsets is found, it returns false.

Step-by-Step Algorithm

1. Input Check:

   • Step 1: If the input array nums has only one element, return false because a single element cannot be split into two non-empty subsets.
   • Step 2: If the input array nums has two elements, return true if both elements are equal, otherwise return false.

2. Initialize Variables:

   • Step 3: Calculate arrayLength, the total number of elements in nums.
   • Step 4: Calculate halfLength, which is half the length of the array, using integer division. This helps us divide the array into two parts.
   • Step 5: Calculate totalSum, which is the sum of all elements in the array nums. This sum will be used later to determine if a valid split is possible.

3. Generate Subsets for Each Half:

   • Step 6: Split the array nums into two parts:
     • First half: contains the first halfLength + 1 elements.
     • Second half: contains the remaining elements.
   • Step 7: Call the generateSubsetSums method on the first half to generate all possible subset sums for this part. The results are stored in a nested array firstHalfSubsetSums, where each index represents the size of the subsets, and each list at that index stores the sums of all subsets of that particular size.
   • Step 8: Generate all possible subset sums for right half.

4. Sort Subset Sums for the Second Half:

   • Step 9: Sort each list in secondHalfSubsetSums in ascending order. Sorting is necessary because it allows us to perform an efficient binary search later when we need to check if a corresponding subset sum exists in the second half.

5. Check for Matching Subsets:

   • Step 10: Iterate through each subset sum in firstHalfSubsetSums using two nested loops:
     • Outer Loop: The outer loop iterates through each possible subset size i in firstHalfSubsetSums.
     • Inner Loop: The inner loop iterates through each subset sum sum1 corresponding to size i.
   • Step 11: For each subset sum sum1 from the first half, iterate through each subset sum in secondHalfSubsetSums using another loop:
     • Skip Invalid Combinations: If the total subset size i + j is either 0 (empty subset) or equals nums.length (the entire array), skip to the next iteration because we need non-empty, proper subsets.
     • Calculate requiredSum: For a valid split, calculate the required sum for the corresponding subset in the second half using the formula:
     • Step 12: If requiredSum is not an integer (i.e., it has a fractional part), skip to the next iteration because only integer subset sums are possible.
     • Step 13: Perform a binary search in secondHalfSubsetSums[j] to check if requiredSum exists in the second half's subsets of size j. If found, return true.

6. Return Result:

   • Step 14: If no valid subset pair is found after all iterations, return false.

How RequiredSum Formula Works?

The formula used to calculate the requiredSum is:

This formula is derived from the condition that the average of the two subsets must be the same. Here's a step-by-step breakdown of how this formula works and how it helps determine the size and sum of the second subset.

Step-by-Step Derivation

1. Average Condition:

   • Let A and B be two non-empty subsets of the original array nums.
   • The average of subset A should equal the average of subset B:

2. Cross Multiplication:

   • Cross multiplying the above equation gives:
   • Rearranging this equation:

3. Total Sum Condition:

   • The sum of all elements in the array nums is:
   • Substituting sum(B) from the previous step:
   • Rearranging this:

4. Simplifying the Expression:

   • To solve for sum(B), rearrange to:
   • This can be further simplified to:
   • This is the requiredSum we use in the algorithm.

Algorithm Walkthrough

Let’s walk through each step of the algorithm in detail for the input nums = [1, 5, 3, 5, 6].

1. Initial Input Check:

   • The array length is 5, which is greater than 2, so we proceed to the next steps.

2. Initialization:

   • arrayLength = 5
   • halfLength = 2 (since 5 // 2 = 2)
   • totalSum = 1 + 5 + 3 + 5 + 6 = 20

3. Generate Subsets:

   • Split nums into two parts:
     • First part: [1, 5, 3]
     • Second part: [5, 6]
   • Call generateSubsetSums on [1, 5, 3]:
   • Subsets generated and their sums:
     • [] -> sum = 0 (size = 0)
     • [1] -> sum = 1 (size = 1)
     • [5] -> sum = 5 (size = 1)
     • [3] -> sum = 3 (size = 1)
     • [1, 5] -> sum = 6 (size = 2)
     • [1, 3] -> sum = 4 (size = 2)
     • [5, 3] -> sum = 8 (size = 2)
     • [1, 5, 3] -> sum = 9 (size = 3)
   • These are stored in the nested array:
     • subsetSums[0] = [0] (subset with 0 elements)
     • subsetSums[1] = [1, 5, 3] (subsets with 1 element)
     • subsetSums[2] = [6, 4, 8] (subsets with 2 elements)
     • subsetSums[3] = [9] (subsets with 3 elements)
   • Call generateSubsetSums on [5, 6]:
     • Subsets generated and their sums:
       • [] -> sum = 0 (size = 0)
       • [5] -> sum = 5 (size = 1)
       • [6] -> sum = 6 (size = 1)
       • [5, 6] -> sum = 11 (size = 2)
     • These are stored in the nested array:
       • subsetSums[0] = [0] (subset with 0 elements)
       • subsetSums[1] = [5, 6] (subsets with 1 element)
       • subsetSums[2] = [11] (subsets with 2 elements)

4. Sort the Second Half Subsets:

   • Sort each list in secondHalfSubsetSums: [ [0], [5, 6], [11] ].

5. Check for Matching Subsets:

   Step-by-Step Matching:

   • For i = 0, subsetSums[0] = [0]:
     • For sum1 = 0:
       • For j = 0, i + j = 0. So, continue to the next iteration.
       • For j = 1, subsetSums[1] = [5, 6]:
         • Calculate requiredSum = - 0 = 4 - 0 = 4.
         • 4 is not found in [5, 6], so continue.
       • For j = 2, subsetSums[2] = [11]:
         • Calculate requiredSum = - 0 = 8 - 0 = 8.
         • 8 is not found in [11], so continue.
   • For i = 1, subsetSums[1] = [1, 5, 3]:
     • For sum1 = 1:
       • For j = 1, subsetSums[1] = [5, 6]:
         • Calculate requiredSum = - 1 = 8 - 1 = 7.
         • 7 is not found in [5, 6], so continue.
       • For j = 2, subsetSums[2] = [11]:
         • Calculate requiredSum = - 1 = 12 - 1 = 11.
         • Perform binary search on [11], and 11 is found.
         • Return true as we found a valid pair.

Code

import java.util.*;

public class Solution {

  // Function to create all subsets of each half of the array
  public List<Integer>[] generateSubsetSums(int[] arrayPart) {
    int halfLength = arrayPart.length; // Get the length of the current half of the array
    List<Integer>[] subsetSums = new List[halfLength + 1]; // Create an array of lists to store subset sums based on their size

    // Initialize each list in the subsetSums array
    for (int i = 0; i <= halfLength; i++) {
      subsetSums[i] = new ArrayList<>();
    }

    // Generating all subsets using an iterative method (power set)
    for (int mask = 0; mask < (1 << halfLength); mask++) {
      int subsetSize = 0,
        subsetSum = 0,
        currentMask = mask,
        index = 0;
      while (currentMask != 0) {
        if ((currentMask & 1) == 1) {
          // Check if the lowest bit is 1 (part of the subset)
          subsetSize++; // Increment the size of the current subset
          subsetSum += arrayPart[index]; // Add the current element to the subset sum
        }
        index++;
        currentMask >>= 1; // Shift right to process the next bit
      }
      subsetSums[subsetSize].add(subsetSum); // Add the sum of this subset to the corresponding list
    }
    return subsetSums; // Return the array of lists with all subset sums
  }

  public boolean splitArraySameAverage(int[] nums) {
    int arrayLength = nums.length;
    if (arrayLength == 1) return false; // A single element cannot be split into two subsets
    if (arrayLength == 2) return nums[0] == nums[1]; // With two elements, they must be equal to split equally

    int halfLength = arrayLength / 2; // Calculate the length of each half
    int totalSum = Arrays.stream(nums).sum(); // Calculate the total sum of the array

    // Generate subset sums for the first half and second half of the array
    List<Integer>[] firstHalfSubsetSums = generateSubsetSums(
      Arrays.copyOfRange(nums, 0, halfLength + 1)
    );
    List<Integer>[] secondHalfSubsetSums = generateSubsetSums(
      Arrays.copyOfRange(nums, halfLength + 1, arrayLength)
    );

    // Sort each list in the second half subset for binary search later
    for (int i = 0; i < halfLength; i++) {
      Collections.sort(secondHalfSubsetSums[i]);
    }

    // Check if we can find two subsets (one from each half) that satisfy the condition
    for (int i = 0; i < firstHalfSubsetSums.length; i++) {
      for (int sum1 : firstHalfSubsetSums[i]) {
        for (int j = 0; j < secondHalfSubsetSums.length; j++) {
          // Skip cases where the subset size is 0 or equal to the total length
          if (i + j == 0 || i + j == nums.length) continue;

          // Calculate the required sum for the second subset
          double requiredSum =
            ((1.0 * totalSum * (i + j)) / nums.length) - sum1;
          if (Math.ceil(requiredSum) != requiredSum) continue; // Check if requiredSum is an integer

          // Check if the required sum exists in the second half subsets using binary search
          if (
            Collections.binarySearch(
              secondHalfSubsetSums[j],
              (int) requiredSum
            ) >=
            0
          ) {
            return true; // If found, return true
          }
        }
      }
    }
    return false; // If no valid subset found, return false
  }

  // Main method to test the code with provided examples
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] nums1 = { 1, 5, 3, 5, 6 };
    System.out.println("Example 1: " + solution.splitArraySameAverage(nums1));

    // Example 2
    int[] nums2 = { 3, 5, 6, 4, 2, 10 };
    System.out.println("Example 2: " + solution.splitArraySameAverage(nums2));

    // Example 3
    int[] nums3 = { 4, 8, 16, 24, 32, 40 };
    System.out.println("Example 3: " + solution.splitArraySameAverage(nums3));
  }
}

Complexity Analysis

Time Complexity

• The main complexity arises from generating subsets for each half of the array. For an array of length n, the subset generation for each half (n/2) will take O(2^(n/2) * (n/2)) time. This is because we generate all possible subsets (which is 2^(n/2)) and for each subset, we calculate its sum, which can take up to O(n/2) time.
• Sorting each subset list for the second half takes O(2^(n/2) * log(2^(n/2)) which simplifies to O(2^(n/2) * (n/2)).
• The final nested loop that checks for the matching subsets runs in O((2^(n/2)2), which again simplifies to O(⁽ⁿ⁾).
• Therefore, the overall time complexity is O(2⁽ⁿ⁾ * (n/2)), where n is the length of the input array.

Space Complexity

• The space complexity is primarily dominated by storing the subset sums for both halves of the array. Since we store all subset sums for n/2 elements, the space complexity is O(2^(n/2)) for each half.
• Therefore, the total space complexity is O(2^(n/2) + 2^(n/2)) = O(2^(n/2))`.