Welcome to Subscribe On Youtube

3712. Sum of Elements With Frequency Divisible by K

Description

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

Solutions

Solution 1: Counting

We use a hash table $\textit{cnt}$ to record the frequency of each number. We traverse the array $\textit{nums}$, and for each number $x$, we increment $\textit{cnt}[x]$ by $1$.

Then, we traverse the hash table $\textit{cnt}$. For each element $x$, if its frequency $\textit{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.

  • 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;
    }
}


  • 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;
    }
};


  • 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)


  • 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
}


  • 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;
}

All Problems

All Solutions