Sum of Elements With Frequency Divisible by K - Video Solutions

Problem 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.