3712. Sum Elements With Frequency Divisible by K Solution

Q: Is Sum of Elements With Frequency Divisible by K easy or hard?

This problem is considered Easy. It focuses on recognizing the frequency counting pattern and using a hash map efficiently. Once the counts are computed, the divisibility check is straightforward.

Q: Sum of Elements With Frequency Divisible by K Python/Java solution

Both Python and Java implementations use a dictionary or HashMap to count frequencies. After building the map, iterate through the key-value pairs and sum keys whose frequency is divisible by k. The logic remains identical across Python, Java, C++, Go, and TypeScript.

Q: How to solve Sum of Elements With Frequency Divisible by K in O(n)?

Use a frequency hash map. Iterate through the array once to count occurrences of each number. After building the map, iterate over its entries and check whether the stored frequency is divisible by k. Add those elements to the sum. Each step uses constant-time hash operations, giving overall O(n) complexity.

Q: What is the best approach for Sum of Elements With Frequency Divisible by K?

The best approach uses a hash map to count element frequencies. First iterate through the array and store counts in a map. Then check each element's frequency and add the element to the result if frequency % k == 0. This method runs in O(n) time with O(n) space.

Q: Is Sum of Elements With Frequency Divisible by K asked at Google/Amazon/Meta?

Problems based on frequency counting and hash maps appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of counting occurrences and applying a condition is a common interview theme.

Q: What data structure is used in Sum of Elements With Frequency Divisible by K?

A hash table (hash map or dictionary) is the main data structure. It maps each element to its frequency in the array. This structure enables constant-time average updates and lookups, making the overall algorithm linear time.

Q: What is the time complexity of Sum of Elements With Frequency Divisible by K?

The optimal solution runs in O(n) time. One pass builds the frequency map and another pass checks the divisibility condition for each unique element. Space complexity is O(n) because the hash map stores counts for distinct values.

The problem

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:

The number 1 appears once (odd frequency).
The number 2 appears twice (even frequency).
The number 3 appears four times (even frequency).
The number 4 appears once (odd frequency).

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:

The number 1 appears once.
The number 2 appears once.
The number 3 appears once.
The number 4 appears three times.

So, the total sum is 4 + 4 + 4 = 12.

Constraints:

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

Approach overview

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.

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

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)

Java

class Solution {
    public int sumDivisibleByK(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        int ans = 0;
        for (var e : cnt.entrySet()) {
            int x = e.getKey(), v = e.getValue();
            if (v % k == 0) {
                ans += x * v;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int sumDivisibleByK(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for (int x : nums) {
            ++cnt[x];
        }
        int ans = 0;
        for (auto& [x, v] : cnt) {
            if (v % k == 0) {
                ans += x * v;
            }
        }
        return ans;
    }
};

TypeScript

function sumDivisibleByK(nums: number[], k: number): number {
    const cnt = new Map();
    for (const x of nums) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    let ans = 0;
    for (const [x, v] of cnt.entries()) {
        if (v % k === 0) {
            ans += x * v;
        }
    }
    return ans;
}

func sumDivisibleByK(nums []int, k int) (ans int) {
    cnt := map[int]int{}
    for _, x := range nums {
        cnt[x]++
    }
    for x, v := range cnt {
        if v%k == 0 {
            ans += x * v
        }
    }
    return
}

Try this approach in the editor

Complexity analysis

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

Frequently asked questions

Is Sum of Elements With Frequency Divisible by K easy or hard?

This problem is considered Easy. It focuses on recognizing the frequency counting pattern and using a hash map efficiently. Once the counts are computed, the divisibility check is straightforward.

Sum of Elements With Frequency Divisible by K Python/Java solution

Both Python and Java implementations use a dictionary or HashMap to count frequencies. After building the map, iterate through the key-value pairs and sum keys whose frequency is divisible by k. The logic remains identical across Python, Java, C++, Go, and TypeScript.

How to solve Sum of Elements With Frequency Divisible by K in O(n)?

Use a frequency hash map. Iterate through the array once to count occurrences of each number. After building the map, iterate over its entries and check whether the stored frequency is divisible by k. Add those elements to the sum. Each step uses constant-time hash operations, giving overall O(n) complexity.

What is the best approach for Sum of Elements With Frequency Divisible by K?

The best approach uses a hash map to count element frequencies. First iterate through the array and store counts in a map. Then check each element's frequency and add the element to the result if frequency % k == 0. This method runs in O(n) time with O(n) space.

Is Sum of Elements With Frequency Divisible by K asked at Google/Amazon/Meta?

Problems based on frequency counting and hash maps appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of counting occurrences and applying a condition is a common interview theme.

What data structure is used in Sum of Elements With Frequency Divisible by K?

A hash table (hash map or dictionary) is the main data structure. It maps each element to its frequency in the array. This structure enables constant-time average updates and lookups, making the overall algorithm linear time.

What is the time complexity of Sum of Elements With Frequency Divisible by K?

The optimal solution runs in O(n) time. One pass builds the frequency map and another pass checks the divisibility condition for each unique element. Space complexity is O(n) because the hash map stores counts for distinct values.

Sum of Elements With Frequency Divisible by K solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Sum of Elements With Frequency Divisible by K solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems