Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

805. Split Array With Same Average

Time: $O(2^{n / 2})$

Space: $O(2^{n / 2})$

			


class Solution {
 public:
  bool splitArraySameAverage(vector<int>& A) {
    const int n = A.size();
    const int sum = accumulate(begin(A), end(A), 0);
    if (!isPossible(sum, n))
      return false;

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

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

    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;
  }
};




			


class Solution {
  public boolean splitArraySameAverage(int[] A) {
    final int n = A.length;
    final int sum = Arrays.stream(A).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 a : A)
      for (int i = n / 2; i > 0; --i)
        for (final int num : sums.get(i - 1))
          sums.get(i).add(a + num);

    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;
  }
}




			


class Solution:
  def splitArraySameAverage(self, A: List[int]) -> bool:
    n = len(A)
    summ = sum(A)
    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 a in A:
      for i in range(n // 2, 0, -1):
        for val in sums[i - 1]:
          sums[i].add(a + 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