Free Hashing lessonsHashing · Stage 3 · Sets for structure · Step 2

In one but not the other

Count the values that belong to exactly one of two lists. About 7 minutes.

Two sets, two questions

Two teams compare their tool lists: which tools does only one team use? Build a set for each list. A tool is only in the first list if the first set has it and the second doesn't, and the other way round for the second list.

Add up both sides and you have every value that's in exactly one list.

Only in the first: in its set, not in the other's.

a = [1, 2, 3], b = [2, 3, 4] · ✓ = in that list's set

1234

set(a)

✓

set(b)

✓

count: 1

1 is in a's set but not b's. Only in one: count it.

Move 1 of 4

Walk the sets, not the lists

If you walked the lists, a value that appears twice would be counted twice. Walking the sets sees each different value exactly once, which is what the question asks for.

For 1, 2, 3 and 2, 3, 4: 1 is only in the first, 4 is only in the second, so the answer is 2.

Walk the lists: and repeats get counted twice.

In code

A, B = set(a), set(b)
only_a = sum(1 for x in A if x not in B)
only_b = sum(1 for x in B if x not in A)
return only_a + only_b

Quick check

The lists are 1, 2, 3 and 2, 3, 4. How many values are in exactly one list?

Show the answer

2. 1 is only in the first, 4 only in the second.

Your problem

Values in exactly one list

Count the distinct values that appear in one of the two lists but not in the other.

Example

a = [1, 2, 3], b = [2, 3, 4] → 2

0 ≤ lengths ≤ 500,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.