leetcode

commit 4fd753a96fff65905a8159ae968acdaec1275654
parent 7d9f4fd9a9e5b846a9fe7e3ff6c794722d045eb6
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon,  3 Nov 2025 19:27:08 -0700

3318. find x-sum of all k-long subarrays 1

Diffstat:
A
find_x_sum_k_subarr1.c
 | 
64
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
find_x_sum_k_subarr1.py
 | 
39
+++++++++++++++++++++++++++++++++++++++

2 files changed, 103 insertions(+), 0 deletions(-)
diff --git a/find_x_sum_k_subarr1.c b/find_x_sum_k_subarr1.c
@@ -0,0 +1,64 @@
+// 3318. Find X-Sum of All K-Long Subarrays I
+#include "leetcode.h"
+
+/*
+ * you are given an array 'nums' of 'n' integers and two integers 'k' and 'x'.
+ * the x-sum of an array is calcluated by the follow procedure: count the
+ * occurences of all elements in the array, keep only the occurences of the top
+ * 'x' most frequent elements. if two elements have the same number of
+ * occurences, the element with the bigger value is considered more frequent.
+ * calcluate the sum of the resulting array. note tht if an array has less than
+ * 'x' distinct eleents, its x-sum is the sum of the array. return an integer
+ * array 'ans' of length 'n - k + 1' where 'ans[i]' is the x-sum of the subarray
+ * 'nums[i .. i + k - 1]'
+ */
+
+struct pair {
+  int num;
+  int freq;
+};
+
+int cmp(const void *a, const void *b) {
+  struct pair *p1 = (struct pair *)a;
+  struct pair *p2 = (struct pair *)b;
+  if (p2->freq != p1->freq)
+    return p2->freq - p1->freq;
+  return p2->num - p1->num;
+}
+
+int *findXSum(int *nums, int numsSize, int k, int x, int *returnSize) {
+  *returnSize = numsSize - k + 1;
+  int *ans = (int *)malloc(*returnSize * sizeof(int));
+  for (int i = 0; i <= numsSize - k; i++) {
+    int freq[51] = {0}, cnt = 0;
+    struct pair kvp[51];
+    for (int j = i; j < i + k; j++)
+      freq[nums[j]]++;
+    for (int j = 1; j <= 50; j++)
+      if (freq[j] > 0) {
+        kvp[cnt].num = j;
+        kvp[cnt].freq = freq[j];
+        cnt++;
+      }
+    qsort(kvp, cnt, sizeof(struct pair), cmp);
+    int sum = 0;
+    for (int j = 0; j < cnt && j < x; j++)
+      sum += kvp[j].num * kvp[j].freq;
+    ans[i] = sum;
+  }
+  return ans;
+}
+
+int main() {
+  int n1[] = {1, 1, 2, 2, 3, 4, 3, 2, 3}, n2[] = {3, 8, 7, 8, 7, 5};
+  int rs1, *fxs1 = findXSum(n1, ARRAY_SIZE(n1), 6, 2, &rs1);
+  int rs2, *fxs2 = findXSum(n2, ARRAY_SIZE(n2), 2, 2, &rs2);
+  for (int i = 0; i < rs1; i++)
+    printf("%d ", fxs1[i]); // expect: 6 10 12
+  printf("\n");
+  for (int i = 0; i < rs2; i++)
+    printf("%d ", fxs2[i]); // expect: 11 15 15 15 12
+  printf("\n");
+  free(fxs1);
+  free(fxs2);
+}
diff --git a/find_x_sum_k_subarr1.py b/find_x_sum_k_subarr1.py
@@ -0,0 +1,39 @@
+# 3318. Find X-Sum of All K-Long Subarrays I
+from collections import Counter
+
+"""
+you are given an array 'nums' of 'n' integers and two integers 'k' and 'x'.
+the x-sum of an array is calcluated by the follow procedure: count the
+occurences of all elements in the array, keep only the occurences of the top
+'x' most frequent elements. if two elements have the same number of
+occurences, the element with the bigger value is considered more frequent.
+calcluate the sum of the resulting array. note tht if an array has less than
+'x' distinct eleents, its x-sum is the sum of the array. return an integer
+array 'ans' of length 'n - k + 1' where 'ans[i]' is the x-sum of the subarray
+'nums[i .. i + k - 1]'
+"""
+
+
+class Solution(object):
+    def findXSum(self, nums, k, x):
+        """
+        :type nums: List[int]
+        :type k: int
+        :type x: int
+        :rtype: List[int]
+        """
+        n, ans = len(nums), []
+        for i in range(n - k + 1):
+            window = nums[i : i + k]
+            freq = Counter(window)
+            sort_freq = sorted(freq.items(), key=lambda x: (-x[1], -x[0]))
+            top_x = set(i for i, _ in sort_freq[:x])
+            x_sum = sum(i for i in window if i in top_x)
+            ans.append(x_sum)
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.findXSum(nums=[1, 1, 2, 2, 3, 4, 2, 3], k=6, x=2))
+    print(obj.findXSum(nums=[3, 8, 7, 8, 7, 5], k=2, x=2))