1 files changed, 64 insertions, 0 deletions
diff --git a/challenge-211/eric-cheung/python/ch-2.py b/challenge-211/eric-cheung/python/ch-2.py
new file mode 100755
index 0000000000..20c7925e9f
--- /dev/null
+++ b/challenge-211/eric-cheung/python/ch-2.py
@@ -0,0 +1,64 @@
+
+## Remarks
+## https://github.com/ChiahungTai/LeetCode/blob/master/Python/split-array-with-same-average.py
+
+
+## Time:  O(n^4)
+## Space: O(n^3)
+
+## In a given integer array A, we must move every element of A to
+## either list B or list C. (B and C initially start empty.)
+##
+## Return true if and only if after such a move, it is possible that
+## the average value of B is equal to the average value of C, and B and C are both non-empty.
+##
+## Example :
+## Input:
+## [1, 2, 3, 4, 5, 6, 7, 8]
+## Output: true
+## Explanation: We can split the array into [1, 4, 5, 8] and [2, 3, 6, 7],
+## and both of them have the average of 4.5.
+##
+## Note:
+## - The length of A will be in the range [1, 30].
+## - A[i] will be in the range of [0, 10000].
+
+class Solution(object):
+
+    def splitArraySameAverage(self, A):
+        """
+        :type A: List[int]
+        :rtype: bool
+        """
+        def possible(total, n):
+            for i in range(1, n // 2 + 1):
+                if total * i % n == 0:
+                    return True
+
+            return False
+
+        n, s = len(A), sum(A)
+
+        if not possible(n, s):
+            return False
+
+        sums = [set() for _ in range(n // 2 + 1)];
+        sums[0].add(0)
+
+        for num in A:  # O(n) times
+            for i in reversed(range(1, n // 2 + 1)):  ## O(n) times
+                for prev in sums[i - 1]:  ## O(1) + O(2) + ... O(n/2) = O(n^2) times
+                    sums[i].add(prev + num)
+
+        for i in range(1, n // 2 + 1):
+            if s * i % n == 0 and s * i // n in sums[i]:
+                return True
+
+        return False
+
+
+## arrInput = [1, 2, 3, 4, 5, 6, 7, 8]  ## Example 1
+arrInput = [1, 3]  ## Example 2
+
+objVar = Solution()
+print (objVar.splitArraySameAverage(arrInput))