Skip to content

805. Split Array With Same Average 👍

  • Time: $O(2^{n / 2})$
  • Space: $O(2^{n / 2})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  bool splitArraySameAverage(vector<int>& nums) {
    const int n = nums.size();
    const int sum = accumulate(nums.begin(), nums.end(), 0);
    if (!isPossible(sum, n))
      return false;

    vector<unordered_set<int>> sums(n / 2 + 1);
    sums[0].insert(0);

    for (const int num : nums)
      for (int i = n / 2; i > 0; --i)
        for (const int val : sums[i - 1])
          sums[i].insert(num + val);

    for (int i = 1; i < n / 2 + 1; ++i)
      if (i * sum % n == 0 && sums[i].count(i * sum / n))
        return true;

    return false;
  }

 private:
  bool isPossible(int sum, int n) {
    for (int i = 1; i < n / 2 + 1; ++i)
      if (i * sum % n == 0)
        return true;
    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public boolean splitArraySameAverage(int[] nums) {
    final int n = nums.length;
    final int sum = Arrays.stream(nums).sum();
    if (!isPossible(sum, n))
      return false;

    List<Set<Integer>> sums = new ArrayList<>();

    for (int i = 0; i < n / 2 + 1; ++i)
      sums.add(new HashSet<>());
    sums.get(0).add(0);

    for (final int num : nums)
      for (int i = n / 2; i > 0; --i)
        for (final int val : sums.get(i - 1))
          sums.get(i).add(num + val);

    for (int i = 1; i < n / 2 + 1; ++i)
      if (i * sum % n == 0 && sums.get(i).contains(i * sum / n))
        return true;

    return false;
  }

  private boolean isPossible(int sum, int n) {
    for (int i = 1; i < n / 2 + 1; ++i)
      if (i * sum % n == 0)
        return true;
    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def splitArraySameAverage(self, nums: List[int]) -> bool:
    n = len(nums)
    summ = sum(nums)
    if not any(i * summ % n == 0 for i in range(1, n // 2 + 1)):
      return False

    sums = [set() for _ in range(n // 2 + 1)]
    sums[0].add(0)

    for num in nums:
      for i in range(n // 2, 0, -1):
        for val in sums[i - 1]:
          sums[i].add(num + val)

    for i in range(1, n // 2 + 1):
      if i * summ % n == 0 and i * summ // n in sums[i]:
        return True

    return False