LeetCode 3712 - Sum of Elements With Frequency Divisible by K

LeetCode Problem 3712

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem asks us to compute the sum of all elements in the array whose total frequency is divisible by a given integer k.

To understand the requirement clearly, we need to focus on two important details:

First, we must determine how many times each number appears in the array. This is the element's frequency.

Second, if a number's frequency is divisible by k, we do not include the number just once. Instead, we include it exactly as many times as it appears in the array.

For example, if the number 3 appears four times and 4 % k == 0, then all four occurrences contribute to the final sum. That means the contribution is 3 + 3 + 3 + 3, or equivalently 3 * 4.

The input consists of:

• nums, an integer array containing values.
• k, an integer divisor used to test whether a frequency qualifies.

The expected output is a single integer representing the total sum of all qualifying elements.

The constraints are quite small:

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

These limits tell us that performance is not a major concern. Even less efficient solutions would still run comfortably within limits. However, we should still aim for a clean and efficient implementation.

There are several important edge cases worth identifying early:

If no number has a frequency divisible by k, the answer should be 0. A naive implementation might accidentally include elements incorrectly or return an uninitialized value.

If all elements qualify, then the result becomes the sum of the entire array.

When k = 1, every frequency is divisible by 1, meaning every element must always be included.

Arrays with only one element are also important. Since frequency equals 1, whether it contributes depends entirely on whether k = 1.

The problem guarantees valid input values, so we do not need to handle invalid or empty arrays.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to compute the frequency of every number separately for each element.

For every number in nums, we can scan the entire array again to count how many times it appears. Once we know the frequency, we check whether it is divisible by k. If it is, we add the number to the result.

This method is correct because it explicitly computes the frequency for every element and applies the condition exactly as described in the problem. However, it performs repeated work. If a number appears many times, we repeatedly recount the same frequency over and over.

Since for every element we may scan the whole array again, the time complexity becomes quadratic.

Optimal Approach, Frequency Counting with a Hash Map

The key observation is that frequency computation should only happen once per distinct number.

Instead of repeatedly scanning the array, we can first build a frequency map using a hash table. The hash map stores each number as a key and its count as the value.

Once we know all frequencies, we iterate through the frequency map. For every number whose frequency is divisible by k, we add its total contribution to the answer.

Rather than adding the number repeatedly, we can directly compute its contribution as:

number × frequency

This works because the problem says to include the number exactly as many times as it appears.

A hash map is ideal here because it gives near constant time insertion and lookup, making frequency counting efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans the array to count frequencies
Optimal	O(n)	O(n)	Uses a hash map to count frequencies once

Algorithm Walkthrough

1. Create a hash map to store frequencies of numbers.

We need an efficient way to count occurrences of every value. A hash map allows us to increment counts in near constant time. 2. Traverse the input array once and populate the frequency map.

For each number in nums, increase its count in the map. After this pass, we know the exact frequency of every distinct number. 3. Initialize a variable called total_sum to 0.

This variable will store the final answer. 4. Iterate through every (number, frequency) pair in the frequency map.

For each unique number, check whether its frequency is divisible by k. 5. If frequency % k == 0, add the contribution to the answer.

Since the problem wants the number included exactly as many times as it appears, add:

number * frequency

instead of repeatedly adding the number. 6. Return total_sum.

After processing all numbers, the accumulated result is the final answer.

Why it works

The algorithm works because it separates the problem into two independent steps: counting frequencies and evaluating divisibility.

The frequency map guarantees that every number's occurrence count is computed correctly exactly once. Then, for each distinct number, we apply the condition frequency % k == 0. If the condition holds, we add the exact contribution required by the problem, namely the number repeated frequency times, which is mathematically equivalent to number × frequency.

Since every unique number is processed exactly once and no qualifying element is missed or double counted, the algorithm always produces the correct result.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def sumDivisibleByK(self, nums: List[int], k: int) -> int:
        frequency = Counter(nums)
        total_sum = 0

        for number, count in frequency.items():
            if count % k == 0:
                total_sum += number * count

        return total_sum

The implementation follows the algorithm directly.

We first use Counter from Python's collections module to build the frequency map in one line. This automatically counts how many times each number appears in nums.

We then initialize total_sum to accumulate the result.

Next, we iterate through each number and its corresponding count in the frequency map. If the count is divisible by k, we add number * count to the answer. This multiplication is equivalent to including the number exactly as many times as it appears.

Finally, we return the accumulated sum.

Go Solution

func sumDivisibleByK(nums []int, k int) int {
	frequency := make(map[int]int)

	for _, num := range nums {
		frequency[num]++
	}

	totalSum := 0

	for num, count := range frequency {
		if count%k == 0 {
			totalSum += num * count
		}
	}

	return totalSum
}

The Go implementation closely mirrors the Python solution, but uses Go's built in map[int]int for frequency counting.

Since Go does not have a built in Counter utility like Python, we manually increment counts with:

frequency[num]++

Go maps return the zero value for missing keys, so incrementing works naturally without requiring initialization.

There are no special nil versus empty concerns here because the problem guarantees a non empty input array. Integer overflow is also not a practical issue due to the small constraints, since the maximum possible sum is very small.

Worked Examples

Example 1

Input:

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

Step 1: Build Frequency Map

Number	Frequency
1	1
2	2
3	4
4	1

Step 2: Process Frequencies

Number	Frequency	Divisible by 2?	Contribution	Running Sum
1	1	No	0	0
2	2	Yes	2 × 2 = 4	4
3	4	Yes	3 × 4 = 12	16
4	1	No	0	16

Final answer:

16

Example 2

Input:

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

Step 1: Build Frequency Map

Number	Frequency
1	1
2	1
3	1
4	1
5	1

Step 2: Process Frequencies

Number	Frequency	Divisible by 2?	Contribution	Running Sum
1	1	No	0	0
2	1	No	0	0
3	1	No	0	0
4	1	No	0	0
5	1	No	0	0

Final answer:

0

Example 3

Input:

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

Step 1: Build Frequency Map

Number	Frequency
4	3
1	1
2	1
3	1

Step 2: Process Frequencies

Number	Frequency	Divisible by 3?	Contribution	Running Sum
4	3	Yes	4 × 3 = 12	12
1	1	No	0	12
2	1	No	0	12
3	1	No	0	12

Final answer:

12

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count frequencies and one pass through distinct elements
Space	O(n)	Hash map stores frequencies of unique elements

The time complexity is linear because we only traverse the array once to count frequencies and then iterate over the unique elements in the map. Since the number of distinct elements cannot exceed n, the total work remains proportional to the input size.

The space complexity is O(n) in the worst case when every number is unique, requiring a frequency entry for every element.

Test Cases

solution = Solution()

assert solution.sumDivisibleByK([1, 2, 2, 3, 3, 3, 3, 4], 2) == 16  # Example 1
assert solution.sumDivisibleByK([1, 2, 3, 4, 5], 2) == 0  # Example 2
assert solution.sumDivisibleByK([4, 4, 4, 1, 2, 3], 3) == 12  # Example 3

assert solution.sumDivisibleByK([5], 1) == 5  # Single element qualifies
assert solution.sumDivisibleByK([5], 2) == 0  # Single element does not qualify

assert solution.sumDivisibleByK([1, 1, 2, 2, 3, 3], 2) == 12  # All frequencies divisible
assert solution.sumDivisibleByK([1, 2, 3], 5) == 0  # k larger than all frequencies

assert solution.sumDivisibleByK([7, 7, 7, 7], 2) == 28  # Repeated element qualifies
assert solution.sumDivisibleByK([7, 7, 7, 7], 3) == 0  # Repeated element does not qualify

assert solution.sumDivisibleByK([1, 2, 2, 2, 3, 3], 1) == 13  # k = 1, all included
assert solution.sumDivisibleByK([100] * 100, 100) == 10000  # Maximum frequency case

Test	Why
[1,2,2,3,3,3,3,4], k=2	Validates mixed qualifying and non qualifying frequencies
[1,2,3,4,5], k=2	Ensures result is zero when nothing qualifies
[4,4,4,1,2,3], k=3	Tests exact divisibility
[5], k=1	Single element that qualifies
[5], k=2	Single element that does not qualify
[1,1,2,2,3,3], k=2	Every element qualifies
[1,2,3], k=5	k larger than all frequencies
[7,7,7,7], k=2	Repeated number qualifies
[7,7,7,7], k=3	Repeated number fails divisibility
k=1 case	Ensures all frequencies qualify
[100] * 100, k=100	Stress test near constraint maximum

Edge Cases

No Elements Qualify

An important edge case occurs when no number has a frequency divisible by k. A buggy implementation might accidentally return an incorrect partial sum or fail to initialize the answer properly.

For example:

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

All frequencies are 1, so nothing qualifies. Our implementation handles this naturally because total_sum starts at 0, and no additions occur.

k = 1

When k equals 1, every integer frequency is divisible by 1. This means the answer should always equal the sum of the entire array.

This case can expose implementations that incorrectly apply divisibility logic or misunderstand the requirement to include elements multiple times. Since our implementation checks count % k == 0, every element automatically qualifies and contributes number × count.

Single Element Array

A one element array is another useful boundary case.

For example:

nums = [5]
k = 2

The frequency is 1, which is not divisible by 2, so the answer should be 0.

If instead:

nums = [5]
k = 1

The answer becomes 5.

Our implementation handles both scenarios correctly because the frequency map works the same regardless of input size.

Large Frequency Relative to k

Another subtle case occurs when an element appears many times but does not divide evenly by k.

For example:

nums = [7,7,7,7]
k = 3

The frequency is 4, which is not divisible by 3, so the entire contribution must be excluded.

Our implementation correctly checks divisibility before adding anything, preventing accidental partial inclusion.