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.
Example 1:
Input: nums = [1,2,2,3,3,3,3,4], k = 2
Output: 16
Explanation:
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:
So, the total sum is 4 + 4 + 4 = 12.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 1001 <= k <= 100Problem Overview: You are given an integer array and a value k. Count how many times each number appears, then sum the values whose frequency is divisible by k. If a number appears f times and f % k == 0, its value contributes to the final sum.
Approach 1: Brute Force Frequency Check (O(n²) time, O(1) space)
The direct approach checks the frequency of every element by scanning the entire array repeatedly. For each element nums[i], iterate through the array again and count how many times it appears. After computing the frequency, check whether frequency % k == 0. If true, add the element to the result while avoiding double counting (for example by only processing the first occurrence). This approach works but performs redundant scans for repeated elements, which leads to O(n²) time complexity. It mainly helps demonstrate the problem logic before optimizing.
Approach 2: Hash Map Counting (O(n) time, O(n) space)
The optimal solution uses a frequency map. Iterate through the array once and store counts in a hash map where the key is the element and the value is its frequency. This step runs in O(n) time with constant-time average hash lookups. After building the frequency map, iterate over each (element, frequency) pair. If frequency % k == 0, add the element to the result.
This method avoids repeated scans because each element is counted once and evaluated once. The total complexity becomes O(n) time and O(n) space due to the frequency map. Problems like this are classic applications of hash tables and frequency counting, especially when working with arrays where duplicate values matter more than ordering.
The key insight is separating the task into two phases: count occurrences first, then evaluate the divisibility condition. Once the frequency distribution is known, determining which elements qualify becomes a simple constant-time check per unique value.
Recommended for interviews: Interviewers expect the hash map counting approach. The brute force method shows you understand the requirement, but the optimized version demonstrates familiarity with frequency maps and reducing repeated work. Implementing counting with a hash table in one pass plus a final scan is the cleanest and most scalable solution.
We use a hash table cnt to record the frequency of each number. We traverse the array nums, and for each number x, we increment cnt[x] by 1.
Then, we traverse the hash table cnt. For each element x, if its frequency 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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Frequency Scan | O(n²) | O(1) | Understanding the logic or when avoiding extra memory is required |
| Hash Map Counting | O(n) | O(n) | General case; optimal for large arrays with repeated elements |
3712. Sum of Elements With Frequency Divisible by K (Leetcode Easy) • Programming Live with Larry • 402 views views
Watch 9 more video solutions →Practice Sum of Elements With Frequency Divisible by K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor