Sum of Unique Elements

ArrayCountingHash Table

Given an array of integers, calculate the sum of elements that appear only once in the array. Return the sum.

Example 1

Input

[
  1,
  2,
  2,
  3,
  4,
  4
]

Output

Explanation. In the array, the elements 1 and 3 appear only once. Their sum is 1 + 3 = 4.

Example 2

Input

Output

Explanation. 20 and 30 appear only once and their sum is 20 + 30 = 50.

Example 3

Input

[
  7,
  7,
  7,
  7
]

Output

Explanation. Every element in the array appears more than once. Therefore, the sum of unique elements is 0.

Example 4

Input

[
  9
]

Output

Explanation. The only element in the array is 9 which appears once. Thus, the result is 9.

Example 5

Input

[
  3,
  7,
  3,
  3,
  1,
  5,
  1
]

Output

Explanation. 7 and 5 appear only once. The sum is 7 + 5 = 12.

Follow-up: How would you optimize your solution if the input constraints were increased substantially?

Constraints:

1. The input array will contain at least one element and at most 100 elements. 2. Each element in the array is an integer ranging from 1 to 100.