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

Your task is to return the sum of all elements in nums whose frequency (the number of times they appear in the array) is divisible by k. If no such elements exist, return 0.

Important detail: When an element qualifies (i.e., its total frequency is divisible by k), it contributes to the sum exactly as many times as it appears in the array — not just once.

For example, if nums = [1, 2, 2, 3, 3, 3] and k = 2:

• The number 1 appears 1 time — 1 % 2 != 0, so it is excluded.
• The number 2 appears 2 times — 2 % 2 == 0, so it contributes 2 + 2 = 4.
• The number 3 appears 3 times — 3 % 2 != 0, so it is excluded.

The answer would be 4.

In short, the problem breaks down into three steps:

1. Count how many times each number appears in nums.
2. Check which numbers have a frequency divisible by k.
3. Sum up those numbers, multiplied by their frequencies (i.e., x * cnt[x] for each qualifying number x).

The problem revolves entirely around one piece of information: how many times each number appears in the array. Without knowing the frequency of a number, we cannot decide whether it should be included in the sum. So the natural first thought is — count everything first, then decide.

This immediately points to using a hash table (or Counter in Python), which is the standard tool for frequency counting. One pass through nums gives us a complete mapping from each distinct number x to its frequency cnt[x].

Once the counts are available, the decision for each number becomes a simple check: is cnt[x] % k == 0?

The other key observation comes from the note in the problem: a qualifying element is counted as many times as it appears, not just once. Rather than adding x repeatedly cnt[x] times, we can capture all of its occurrences in a single multiplication — x * cnt[x]. This turns the final step into a clean aggregation:

• For each distinct number x with frequency v, if v % k == 0, add x * v to the answer.

So the approach falls out naturally from two ideas:

1. Frequency is the deciding factor → count occurrences with a hash table.
2. Each occurrence contributes to the sum → multiply the value by its frequency instead of summing duplicates one by one.

This gives a straightforward solution that runs in O(n) time with O(n) extra space, where n is the length of nums — a single pass to count, and a single pass over the distinct values to sum.

Pattern used: Counting with a hash table.

The implementation follows two simple phases — count, then aggregate.

Step 1: Count the frequency of each number

We use a hash table cnt to record how many times each number appears:

cnt = Counter(nums)

Counter(nums) traverses the array once. For each number x, it increments cnt[x] by 1. After this pass, cnt maps every distinct value in nums to its total frequency. This is equivalent to writing:

cnt = {}
for x in nums:
    cnt[x] = cnt.get(x, 0) + 1

Step 2: Sum the qualifying elements

Next, we traverse the hash table. For each entry (x, v) — where x is the number and v is its frequency — we check whether v is divisible by k:

• If v % k == 0, the number qualifies. Since it must be counted once per occurrence, it contributes x * v to the total.
• Otherwise, it contributes nothing.

This is expressed compactly with a generator expression:

return sum(x * v for x, v in cnt.items() if v % k == 0)

If no element satisfies the condition, the generator yields nothing and sum returns 0, which matches the required default — no special-case handling is needed.

Full Code

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)

Walkthrough Example

Take nums = [1, 2, 2, 3, 3, 3, 3] and k = 2:

1. Counting gives cnt = {1: 1, 2: 2, 3: 4}.
2. Checking each entry:
   • 1 has frequency 1 → 1 % 2 != 0 → skipped.
   • 2 has frequency 2 → 2 % 2 == 0 → contributes 2 * 2 = 4.
   • 3 has frequency 4 → 4 % 2 == 0 → contributes 3 * 4 = 12.
3. Final answer: 4 + 12 = 16.

Complexity Analysis

• Time complexity: O(n), where n is the length of nums. One pass to build the counter and one pass over at most n distinct keys.
• Space complexity: O(n) in the worst case, when all elements in nums are distinct and the hash table stores n entries.

Alternative Perspective

A sorting-based approach is also possible: sort the array, scan groups of equal values, and add each group's total x * groupSize when groupSize % k == 0. This reduces extra space to O(1) (ignoring sort space) but raises time to O(n log n), making the hash table approach the better default choice.