leetcode

commit ba52fe64364e4a40338abaa02ed5aa90069b18f5
parent e8467a9e01906a03a1ecb58ae70f9af7dbd1e1ba
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue, 11 Nov 2025 08:41:20 -0700

805. split array with same average

Diffstat:
A
split_arr_same_avg.c
 | 
38
++++++++++++++++++++++++++++++++++++++
A
split_arr_same_avg.py
 | 
38
++++++++++++++++++++++++++++++++++++++

2 files changed, 76 insertions(+), 0 deletions(-)
diff --git a/split_arr_same_avg.c b/split_arr_same_avg.c
@@ -0,0 +1,38 @@
+// 805. Split Array With Same Average
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums'. you should move each element of 'nums'
+ * into one of the two arrays 'a' and 'b' such that 'a' and 'b' are non-empty
+ * and 'average(a) == average(b)'. return true if it is possible to achieve, and
+ * false otherwise. note that for an array 'arr', 'average(arr)' is the sum of
+ * all the elements of the length of 'arr'.
+ */
+
+bool splitArraySameAverage(int *nums, int numsSize) {
+  if (numsSize <= 1)
+    return false;
+  int sum = 0;
+  for (int i = 0; i < numsSize; i++)
+    sum += nums[i];
+  int *dp = (int *)calloc(sum + 1, sizeof(int));
+  dp[nums[0]] = 2;
+  for (int i = 1; i < numsSize; i++) {
+    for (int j = sum - nums[i]; j >= 0; j--)
+      if (dp[j])
+        dp[j + nums[i]] |= (dp[j] << 1);
+    dp[nums[i]] |= 2;
+  }
+  bool ans = false;
+  for (int i = 1; i < numsSize; i++)
+    if (!((sum * i) % numsSize) && ((1 << i) & dp[sum * i / numsSize]))
+      ans = true;
+  free(dp);
+  return ans;
+}
+
+int main() {
+  int n1[] = {1, 2, 3, 4, 5, 6, 7, 8}, n2[] = {3, 1};
+  printf("%d\n", splitArraySameAverage(n1, ARRAY_SIZE(n1))); // expect: 1
+  printf("%d\n", splitArraySameAverage(n2, ARRAY_SIZE(n2))); // expect: 0
+}
diff --git a/split_arr_same_avg.py b/split_arr_same_avg.py
@@ -0,0 +1,38 @@
+# 805. Split Array With Same Average
+
+"""
+you are given an integer array 'nums'. you should move each element of 'nums'
+into one of the two arrays 'a' and 'b' such that 'a' and 'b' are non-empty
+and 'average(a) == average(b)'. return true if it is possible to achieve, and
+false otherwise. note that for an array 'arr', 'average(arr)' is the sum of
+all the elements of the length of 'arr'.
+"""
+
+
+class Solution(object):
+    def possible_sum(self, arr):
+        subset = 1
+        for i in arr:
+            subset |= subset << i
+        return (subset - 1) ^ (1 << sum(arr))
+
+    def splitArraySameAverage(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: bool
+        """
+        n, total = len(nums), sum(nums)
+        if n <= 1:
+            return False
+        transform = [n * i - total for i in nums]
+        if 0 in transform:
+            return True
+        pos = [i for i in transform if i > 0]
+        neg = [-i for i in transform if i < 0]
+        return bool(self.possible_sum(pos) & self.possible_sum(neg))
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.splitArraySameAverage(nums=[1, 2, 3, 4, 5, 6, 7, 8]))
+    print(obj.splitArraySameAverage(nums=[3, 1]))