ITPEC FE Subject B October 2025 Question 16

Jaccard similarity: initializing the union counter

The function computes J(A, B) = |A∩B| / |A∪B| by iterating over A and checking each element against B.

• •iCount tracks |A∩B| (incremented when A[i] is found in B)
• •uCount tracks |A∪B| but is built incrementally: it starts at some initial value, and for each A[i] not found in B, uCount is incremented by 1

After the loop, uCount = initial + (nA - iCount), because nA - iCount elements of A have no match in B.

We need uCount = |A∪B| = nA + nB - iCount, so:

initial + nA - iCount = nA + nB - iCount → initial = nB

Why not others:
- 0 → uCount would only count A's unique elements, missing all of B
- nA → would give 2·nA - iCount, overcounting A
- nA + nB → would double-count the intersection
- nA - nB, nA ÷ nB, nA × nB → no algebraic path to |A∪B|

Key rule: |A∪B| = |A| + |B| - |A∩B|. When a loop adds A's unique elements one by one, initialize the counter with |B| to cover B's contribution upfront.

AI-generated — may contain errors