Count Integers That Appear Exactly Once

Given an array of integers, count how many distinct numbers occur exactly once.

Function Contract

Implement count_single_occurrences(numbers) -> int.

A number contributes one to the answer if its frequency in the entire array is exactly one.

Constraints and Clarifications

These numeric bounds are explicit practice assumptions.

• 0 <= len(numbers) <= 200000.
• Each value is an integer from -1000000000 through 1000000000.
• Repeated values do not contribute, regardless of where their occurrences appear.
• Return 0 for an empty array.
• Aim for expected O(n) time.

Examples

numbers = [4, 2, 1, 4, 4, 1, 3]
Output: 2

Only 2 and 3 appear once.

numbers = [5, 5, -1, -1]
Output: 0

Hint: The first occurrence is not necessarily the only occurrence

Determine the final frequency before deciding whether a value contributes to the answer.

Count Values That Appear Exactly Once

Given an array of integers numbers, count how many distinct values occur exactly once in the array.

A value contributes exactly one to the answer if its frequency in the entire array is exactly one. A value that occurs two or more times contributes nothing, regardless of where in the array its occurrences appear. Return 0 for an empty array.

The result is a single integer count, so there is no ordering or tie-breaking choice to make. Because the array holds at most 200000 elements, the answer is at most 200000 and always fits in a signed 32-bit integer (Java int, C++ int); no intermediate value can exceed 2^31-1 either, since each element lies within -1000000000 through 1000000000 and no sums or products are required.

Aim for expected O(n) time.

Example 1:

numbers = [4, 2, 1, 4, 4, 1, 3]
Output: 2

The value 4 occurs three times and 1 occurs twice, so neither contributes. Only 2 and 3 occur exactly once.

Example 2:

numbers = [5, 5, -1, -1]
Output: 0

Both 5 and -1 occur twice, so nothing contributes and the answer is 0.

Constraints:

• 0 <= len(numbers) <= 200000.
• Each value is an integer from -1000000000 through 1000000000.
• Repeated values do not contribute, regardless of where their occurrences appear.
• Return 0 for an empty array.
• Aim for expected O(n) time.

Hints

1. The first time you meet a value tells you nothing final: the same value may appear again later in the array.
2. Decide whether a value contributes only after the frequency of every value across the entire array is known.
3. An empty array contains no values at all, so its answer is 0.

Approach

Algorithm: make one pass over the array building a hash map from value to its frequency, then make one pass over the map's entries and count how many have frequency exactly 1.

Invariant: after processing the first k elements, counts[v] equals the number of occurrences of v among those k elements, and every value seen so far is a key of the map. When k reaches len(numbers) the map therefore holds the final frequency of every distinct value in the whole array, and no value is missing.

Correctness: the specification says a value contributes one to the answer exactly when its frequency in the entire array is one. The second pass evaluates that predicate against the final frequency of each distinct value, and each distinct value is examined exactly once because it is a single map key, so the sum of contributions equals the number of distinct values with frequency one. Deciding during the first pass would be wrong: a value seen once so far may recur later, which is why the decision is deferred until all frequencies are final. Positions of occurrences are irrelevant to the predicate, so non-adjacent duplicates are handled identically to adjacent ones.

Edge cases: an empty array produces an empty map and the loop adds nothing, returning 0 as required. A singleton array yields one key with frequency 1, returning 1. An array of identical values yields one key with frequency n >= 2, returning 0. Negative values, zero, and the extreme bounds -1000000000 and 1000000000 are ordinary hash keys and need no special handling. The answer is bounded by the number of distinct values, at most 200000, so no overflow is possible in any language; Java and C++ use int, and JavaScript numbers are exact well below 2^53.

Complexity: expected O(n) time with O(n) auxiliary space for the frequency map, matching the requested expected O(n) target.

• Time complexity: O(n)
• Space complexity: O(n)