Skip to content

3712. Sum of Elements With Frequency Divisible by K

Description

You are given an integer array nums and an integer k.

Return an integer denoting the sum of all elements in nums whose frequency is divisible by k, or 0 if there are no such elements.

Note: An element is included in the sum exactly as many times as it appears in the array if its total frequency is divisible by k.

The frequency of an element x is the number of times it occurs in the array.

 

Example 1:

Input: nums = [1,2,2,3,3,3,3,4], k = 2

Output: 16

Explanation:

  • The number 1 appears once (odd frequency).
  • The number 2 appears twice (even frequency).
  • The number 3 appears four times (even frequency).
  • The number 4 appears once (odd frequency).

So, the total sum is 2 + 2 + 3 + 3 + 3 + 3 = 16.

Example 2:

Input: nums = [1,2,3,4,5], k = 2

Output: 0

Explanation:

There are no elements that appear an even number of times, so the total sum is 0.

Example 3:

Input: nums = [4,4,4,1,2,3], k = 3

Output: 12

Explanation:

  • The number 1 appears once.
  • The number 2 appears once.
  • The number 3 appears once.
  • The number 4 appears three times.

So, the total sum is 4 + 4 + 4 = 12.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100

Solutions

Solution 1: Counting

We use a hash table \(\textit{cnt}\) to record the frequency of each number. We traverse the array \(\textit{nums}\), and for each number \(x\), we increment \(\textit{cnt}[x]\) by \(1\).

Then, we traverse the hash table \(\textit{cnt}\). For each element \(x\), if its frequency \(\textit{cnt}[x]\) is divisible by \(k\), we add \(x\) multiplied by its frequency to the result.

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(m)\), where \(m\) is the number of distinct elements in the array.

1
2
3
4
class Solution:
    def sumDivisibleByK(self, nums: List[int], k: int) -> int:
        cnt = Counter(nums)
        return sum(x * v for x, v in cnt.items() if v % k == 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int sumDivisibleByK(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        int ans = 0;
        for (var e : cnt.entrySet()) {
            int x = e.getKey(), v = e.getValue();
            if (v % k == 0) {
                ans += x * v;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int sumDivisibleByK(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for (int x : nums) {
            ++cnt[x];
        }
        int ans = 0;
        for (auto& [x, v] : cnt) {
            if (v % k == 0) {
                ans += x * v;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func sumDivisibleByK(nums []int, k int) (ans int) {
    cnt := map[int]int{}
    for _, x := range nums {
        cnt[x]++
    }
    for x, v := range cnt {
        if v%k == 0 {
            ans += x * v
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function sumDivisibleByK(nums: number[], k: number): number {
    const cnt = new Map();
    for (const x of nums) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    let ans = 0;
    for (const [x, v] of cnt.entries()) {
        if (v % k === 0) {
            ans += x * v;
        }
    }
    return ans;
}

Comments