## Sum Distinct Items

### August 20, 2019

We have an interview question today:

In a list of integers, find the sum of the integers that appear only once. For instance, in the list [4 2 3 1 7 4 2 7 1 7 5], the integers 1, 2, 4 and 7 appear more than once, so they are excluded from the sum, and the correct anser is 3 + 5 = 8.

Your task is to write a program to find the sum of the distinct integers in a list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

In Python it is easy using a Counter.

Here is a solution in standard R7RS Scheme with hash-tables of SRFI

69. It runs in linear time (modulo usual hashing caveats).

Output:

Klong version

Rust generic version, no hash table required:

Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ace1791e4d6532b0bb39c4d5f4b3eb99

Rust generic version, no hash table required:

Rust generic version, no hash table required:

Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ace1791e4d6532b0bb39c4d5f4b3eb99

Paul beat me to it:

Here’s a Haskell version. We’ll say the empty list sums to 0.

Here’s some C++, using a hash table (‘unordered_map’) to store element counts, and a sorting solution, both use the “increment on first occurrence, decrement on second, subsequently ignore” approach, though for the sorting solution it’s probably better to just count the elements, as in Bill’s solution above.

Interestingly, for a million items, the sorting method is significantly faster than the hash table method (about 160ms, vs. 500ms or so).

Here is my take on this, without using any auxiliary functions from packages, in Julia 1.1:

function main(x::Array{Int64, 1})

s = 0

n = length(x)

end

Cheers!

Here’s a solution in C.

Output:

My last solution should work, but the load factor of the hash table could reach 1. This was from mistakenly using the wrong variable on lines 10 and 13. Here’s the fixed solution, which limits the load factor to 0.7.

Java version: