Sum of All Odd Frequency Elements in an Array

The sum of all odd-frequency elements in an array is one of the most direct hash-map problems in campus placement tests.

The task is specific: given an integer array, find every element whose frequency is an odd number, then return the sum of all those occurrences, not just their unique values. One pass to count, one pass to sum. Two loops, one data structure, O(n) time.

The Problem and the Canonical Example

Given an integer array, identify every element that appears an odd number of times. Sum all of their occurrences.

• Input: arr = {1, 2, 4, 5, 6, 3, 1, 2, 3, 3}
• Frequency table:

Element	Count	Odd frequency?	Contribution to sum
1	2	No	0
2	2	No	0
4	1	Yes	4 × 1 = 4
5	1	Yes	5 × 1 = 5
6	1	Yes	6 × 1 = 6
3	3	Yes	3 × 3 = 9

• Expected output: 4 + 5 + 6 + 9 = 24

Three points worth noting before writing any code:

• Element 3 contributes 9 to the sum, not 3. Its three occurrences all count toward the total.
• Elements 1 and 2 contribute nothing because their frequencies (both 2) are even.
• An empty array returns 0 by convention.

The most common wrong answer is 18, produced by misreading “sum of odd-frequency elements” as “add the element value once per odd-frequency element”: 4 + 5 + 6 + 3 = 18. The correct reading sums all occurrences, so element 3’s three appearances add 9 to the total.

Algorithm: Frequency Map, Then Filtered Sum

The solution has two logical phases:

Phase 1: Build the Frequency Map

• Initialise an empty hash map (freq).
• Walk the array from left to right.
• For each element, increment its count in the map.

After one traversal, every distinct value in the array has an entry in freq with its total occurrence count. This phase visits each element exactly once.

Phase 2: Sum the Odd-Frequency Elements

• Initialise sum = 0.
• Iterate over every (element, count) pair in the map.
• If count % 2 != 0, add element * count to sum.
• Return sum.

No secondary data structure is needed. Total space beyond the input: O(k), where k is the number of distinct elements. In the worst case, every element is unique and k equals n.

Implementations in C++, Java, and Python

C++

C++11 and later provide std::unordered_map, which gives O(1) average-case insertion and lookup via hashing. It is the standard choice for frequency-count problems in competitive programming and placement coding rounds.

#include <bits/stdc++.h>
using namespace std;

int sumOddFrequency(vector<int>& arr) {
    unordered_map<int, int> freq;
    for (int x : arr) {
        freq[x]++;
    }

    int sum = 0;
    for (auto& [elem, count] : freq) {
        if (count % 2 != 0) {
            sum += elem * count;
        }
    }
    return sum;
}

int main() {
    vector<int> arr = {1, 2, 4, 5, 6, 3, 1, 2, 3, 3};
    cout << sumOddFrequency(arr) << "\n";  // Output: 24
    return 0;
}

The structured binding auto& [elem, count] (C++17) makes the iteration concise. For C++11 or C++14, replace it with auto& p and use p.first and p.second.

Java

Java’s HashMap provides the same O(1) average-case behaviour. The merge method handles the count increment in one line.

import java.util.HashMap;

public class OddFrequencySum {
    public static int sumOddFrequency(int[] arr) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int x : arr) {
            freq.merge(x, 1, Integer::sum);
        }
        int sum = 0;
        for (var entry : freq.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                sum += entry.getKey() * entry.getValue();
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 6, 3, 1, 2, 3, 3};
        System.out.println(sumOddFrequency(arr));  // Output: 24
    }
}

merge(key, 1, Integer::sum) is equivalent to getOrDefault(key, 0) + 1 but avoids the explicit null check. Both forms are acceptable in placement submissions.

Python

collections.Counter wraps the frequency-map construction into a single call. The generator expression in sum() handles the filtering inline.

from collections import Counter

def sum_odd_frequency(arr):
    freq = Counter(arr)
    return sum(elem * count for elem, count in freq.items() if count % 2 != 0)

arr = [1, 2, 4, 5, 6, 3, 1, 2, 3, 3]
print(sum_odd_frequency(arr))  # Output: 24

Counter is a subclass of dict, so .items() works identically to a plain dictionary. The one-liner is idiomatic Python; expand it into a for-loop if clarity is preferred in a live interview.

All three implementations produce 24 for the canonical input. The logic is identical across languages; only the map API differs.

Tracing the Canonical Example Step by Step

Walking through arr = {1, 2, 4, 5, 6, 3, 1, 2, 3, 3} in Phase 1:

• Read 1: freq becomes {1: 1}
• Read 2: freq becomes {1: 1, 2: 1}
• Read 4: freq becomes {1: 1, 2: 1, 4: 1}
• Read 5: freq becomes {1: 1, 2: 1, 4: 1, 5: 1}
• Read 6: freq becomes {1: 1, 2: 1, 4: 1, 5: 1, 6: 1}
• Read 3: freq becomes {1: 1, 2: 1, 4: 1, 5: 1, 6: 1, 3: 1}
• Read 1: freq becomes {1: 2, 2: 1, 4: 1, 5: 1, 6: 1, 3: 1}
• Read 2: freq becomes {1: 2, 2: 2, 4: 1, 5: 1, 6: 1, 3: 1}
• Read 3: freq becomes {1: 2, 2: 2, 4: 1, 5: 1, 6: 1, 3: 2}
• Read 3: freq becomes {1: 2, 2: 2, 4: 1, 5: 1, 6: 1, 3: 3}

Phase 2 filter and accumulate:

• Element 1, count 2: even, skip
• Element 2, count 2: even, skip
• Element 4, count 1: odd, sum += 4 × 1 = 4
• Element 5, count 1: odd, sum += 5 × 1 = 5
• Element 6, count 1: odd, sum += 6 × 1 = 6
• Element 3, count 3: odd, sum += 3 × 3 = 9

Running totals: 4, 9, 15, 24. Final sum = 24.

Complexity Analysis

	Time	Space
Phase 1 (build frequency map)	O(n)	O(k)
Phase 2 (filter and sum)	O(k)	O(1)
Total	O(n)	O(k)

Here, n is the array length and k is the number of distinct elements. In the worst case, all elements are unique: k = n and space is O(n). When the array has few distinct values, k is small and the map stays compact.

The unordered_map O(1) average case depends on a good hash function for the key type. The standard library provides one for integers, so the constant factor is low in practice.

A sort-based alternative exists: sort the array in O(n log n), then scan consecutive equal-valued runs to compute frequencies. It avoids the O(k) hash map space but is strictly slower. In placement tests, the O(n) hash map approach is the expected answer unless the problem explicitly prohibits extra space.

Where This Pattern Appears in Placement Tests

Frequency-map problems appear in three formats across Indian campus assessment platforms:

• Direct: sum (or count) elements by their frequency, exactly the problem above. AMCAT Automata and the TCS NQT coding round both include this variant.
• Filtered: find all elements that appear exactly once, or more than k times. Same hash-map structure, different filter condition on the count.
• Maximum frequency: find the element with the highest occurrence count. One extra variable tracks the current maximum as you iterate the map in Phase 2.

Two mistakes account for most wrong submissions in placement tests: initialising sum to a non-zero value, and adding just the element value instead of element * count. An interviewer who follows up with “what if I want the count of odd-frequency elements instead of their sum?” is checking whether you understand the separation between Phase 1 and Phase 2.

For a broader list of array and map patterns that appear across online assessments, see data structures interview questions. The linear-scan discipline used in finding the minimum and maximum in an array applies the same single-pass thinking: initialise a candidate, walk once, update on a condition.

The hash map frequency pattern is not limited to placement practice. Tokenizers in large language models use the same counting logic to measure how often each word or subword appears in a training corpus before building a vocabulary. TinkerLLM at ₹299 makes that connection concrete: exercises start from frequency problems like this one and progress toward LLM tokenization tasks, showing that the data structure choice here directly shapes how models represent text.

For another coding problem using the same traversal mindset, see palindrome check.