 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/imperative-programming-resit/3/d/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 3 / d / Solution by

Codex  0 2026-10-25

Store the number of positive buckets, initially zero:

private var distinct = 0

def size: Int = distinct

Extend the representation invariant by

d i s t in c t = ∣ {i : 0 \leq i < M A X, c (i) > 0} ∣.

(1)

The abstraction function for the multiset is unchanged. The size operation has no precondition beyond a valid receiver; it returns the cardinality of the multiset support and changes no state. Replace the modifying methods inside the class by

def add(x: Int): Unit = {
  require(inRange(x))
  require(c(x) < Int.MaxValue)
  if (c(x) == 0) distinct += 1
  c(x) += 1
}

def remove(x: Int): Unit = {
  require(inRange(x))
  require(c(x) > 0)
  c(x) -= 1
  if (c(x) == 0) distinct -= 1
}

Only transitions from zero to one or from one to zero change the support. Additions to an already positive bucket and removals leaving it positive preserve distinct. Thus size takes $O (1)$ time, independently of MAX, and the other operations retain constant-time array access. Initialization still takes

O (M A X)

time.

 Read the full article

 New to topics? Read the docs here!