Split Array With Same Average - Practice Coding Problems

Split Array With Same Average - Problem

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: For an array arr, average(arr) is the sum of all the elements of arr over the length of arr.

Input & Output

Example 1 — Possible Split

$ Input: nums = [1,2,3,4,5,6,7,8]

› Output: true

💡 Note: We can split into {1,4,5,8} with average 4.5 and {2,3,6,7} with average 4.5

Example 2 — Impossible Split

$ Input: nums = [3,1]

› Output: false

💡 Note: Cannot split 2 elements into two non-empty groups with same average

Example 3 — Equal Elements

$ Input: nums = [1,1,1,1]

› Output: true

💡 Note: Any split like {1,1} and {1,1} will have the same average of 1.0

Constraints

1 ≤ nums.length ≤ 30
0 ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [1,2,3,4,5,6] with total sum 21, avg 3.5

Find Partition

Look for two non-empty subsets with equal averages

Verify Solution

Check if {1,4,5} avg=3.33 and {2,3,6} avg=3.67

Key Takeaway

🎯 Key Insight: If avg(A) = avg(B), then both equal the total average sum/n

Asked in

G Google 8 f Facebook 5 M Microsoft 3

The key insight is that if two subsets have equal averages, they both equal the total average. Use dynamic programming to track all possible (sum, count) pairs and check if any valid partition exists. Best approach uses DP with mathematical optimization. Time: O(n × 2ⁿ), Space: O(2ⁿ)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Partitions	O(2ⁿ)	O(n)	Generate all possible ways to split array into two non-empty subsets
2D DP with Bitmask Optimization	O(n² × sum)	O(n × sum)	Use 2D DP to track all possible subset sums and sizes efficiently
Mathematical Optimization with DP	O(n × 2ⁿ)	O(2ⁿ)	Use math insight: if averages are equal, both equal total average

Brute Force - Try All Partitions — Algorithm Steps

Generate all possible non-empty subsets
For each subset, calculate its average and the complement's average
Return true if any partition has equal averages

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Try all 2^n ways to partition array

Check Averages

Calculate average of each partition

Compare

Return true if averages match

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool backtrack(int* nums, int index, long long sumA, int countA, long long totalSum, int n) {
    if (index == n) {
        if (countA == 0 || countA == n) {
            return false;
        }
        int countB = n - countA;
        long long sumB = totalSum - sumA;
        return sumA * countB == sumB * countA;
    }
    
    // Include in subset A
    if (backtrack(nums, index + 1, sumA + nums[index], countA + 1, totalSum, n)) {
        return true;
    }
    
    // Include in subset B
    if (backtrack(nums, index + 1, sumA, countA, totalSum, n)) {
        return true;
    }
    
    return false;
}

bool solution(int* nums, int n) {
    long long totalSum = 0;
    for (int i = 0; i < n; i++) totalSum += nums[i];
    
    return backtrack(nums, 0, 0, 0, totalSum, n);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[30];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(nums, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Must check all 2^n possible subsets of the array

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

22.3K Views

Medium Frequency

~45 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Partitions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler