iframe-proxy | Sunbelt Computer Software

40 lines (37 loc) · 1.08 KB

// Time:  O(n^4)
// Space: O(n^3)
class Solution {
    bool splitArraySameAverage(vector<int>& A) {
        const int n = A.size();
        const int sum = accumulate(A.cbegin(), A.cend(), 0);
        if (!possible(n, sum)) {
            return false;
        vector<unordered_set<int>> sums(n / 2 + 1);
        sums[0].emplace(0);
        for (const auto& num: A) {                      // O(n) times
            for (int i = n / 2; i >= 1; --i) {          // O(n) times
                for (const auto& prev : sums[i - 1]) {  // O(1) + O(2) + ... O(n/2) = O(n^2) times
                    sums[i].emplace(prev + num);
        for (int i = 1; i <= n / 2; ++i) {
            if (sum * i % n == 0 &&
                sums[i].count(sum * i / n)) {
                return true;
        return false;
    bool possible(int n, int sum) {
        for (int i = 1; i <= n / 2; ++i)  {
            if (sum * i % n == 0) {
                return true;
        return false;

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

split-array-with-same-average.cpp

Latest commit

History

split-array-with-same-average.cpp

File metadata and controls