Sum of Elements With Frequency Divisible by K

Difficulty: Easy | Acceptance: 77.90% | Paid: No Topics: Array, Hash Table, Counting

You are given an integer array nums and an integer k. You need to find the sum of all elements in the array whose frequency (number of occurrences) is divisible by k.

Return the sum of all such elements.

Table of Contents

• Examples
• Constraints
• Hash Map Frequency Counting
• Sorting and Counting
• Brute Force

Examples

Example 1

Input: nums = [1,2,3,1,2], k = 2
Output: 3
Explanation: 
- The frequency of 1 is 2 (divisible by 2)
- The frequency of 2 is 2 (divisible by 2)
- The frequency of 3 is 1 (not divisible by 2)
- Sum = 1 + 2 = 3

Example 2

Input: nums = [1,2,3,4,5], k = 1
Output: 15
Explanation: All elements have frequency 1, which is divisible by 1. Sum = 1 + 2 + 3 + 4 + 5 = 15

Example 3

Input: nums = [2,2,2,2,3,3,3,3], k = 4
Output: 5
Explanation: 
- The frequency of 2 is 4 (divisible by 4)
- The frequency of 3 is 4 (divisible by 4)
- Sum = 2 + 3 = 5

Constraints

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁵

Hash Map Frequency Counting

Intuition Use a hash map to count the frequency of each element, then sum elements whose frequency is divisible by k.

Steps

• Create a hash map to store element frequencies
• Iterate through nums and count each element’s frequency
• Iterate through the hash map and sum elements where frequency % k == 0
• Return the sum

class Solution:
    def sumOfElements(self, nums: List[int], k: int) -> int:
        from collections import Counter
        
        freq = Counter(nums)
        total = 0
        
        for num, count in freq.items():
            if count % k == 0:
                total += num
        
        return total

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Most efficient approach for this problem

Sorting and Counting

Intuition Sort the array first, then count consecutive elements to determine frequencies without extra space.

Steps

• Sort the array in ascending order
• Iterate through the sorted array, counting consecutive identical elements
• When a different element is encountered, check if the count is divisible by k
• If yes, add the element to the sum
• Handle the last element separately

class Solution:
    def sumOfElements(self, nums: List[int], k: int) -> int:
        if not nums:
            return 0
        
        nums.sort()
        total = 0
        count = 1
        
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                count += 1
            else:
                if count % k == 0:
                    total += nums[i-1]
                count = 1
        
        # Handle last element
        if count % k == 0:
            total += nums[-1]
        
        return total

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on sorting implementation
• Notes: Slower than hash map but uses less space

Brute Force

Intuition For each unique element, count its occurrences by scanning the entire array, then check divisibility.

Steps

• Iterate through each element in the array
• For each element, count its total occurrences in the array
• If the count is divisible by k and we haven’t processed this element yet, add it to the sum
• Use a set to track processed elements

class Solution:
    def sumOfElements(self, nums: List[int], k: int) -> int:
        processed = set()
        total = 0
        
        for num in nums:
            if num in processed:
                continue
            
            count = nums.count(num)
            if count % k == 0:
                total += num
            
            processed.add(num)
        
        return total

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: Inefficient for large inputs, included for educational purposes