diff options
| author | 冯昶 <fengchang@novel-supertv.com> | 2023-04-10 18:31:25 +0800 |
|---|---|---|
| committer | 冯昶 <fengchang@novel-supertv.com> | 2023-04-10 18:31:25 +0800 |
| commit | 6b7fd386eb2e4b8b700fb12f6a7ca043baa6164c (patch) | |
| tree | 5a04aa69760f2e25d68ed407c5c7fd9867e7ebcc /challenge-211/eric-cheung/python/ch-2.py | |
| parent | 1b193b53c1db2f37be5ccca5ce8ab4545df4f607 (diff) | |
| parent | 4eb9782a746173721822a9ffa29d6f14297a6dca (diff) | |
| download | perlweeklychallenge-club-6b7fd386eb2e4b8b700fb12f6a7ca043baa6164c.tar.gz perlweeklychallenge-club-6b7fd386eb2e4b8b700fb12f6a7ca043baa6164c.tar.bz2 perlweeklychallenge-club-6b7fd386eb2e4b8b700fb12f6a7ca043baa6164c.zip | |
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to 'challenge-211/eric-cheung/python/ch-2.py')
| -rwxr-xr-x | challenge-211/eric-cheung/python/ch-2.py | 64 |
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))
|