Hey guys its me Patrick back with another epic AUCPL editorial. Make sure to follow all our socials so you stay up to date with the latest in AUCPL and ACPC news and enable notifications so you never miss an event.
We are given a list of unique integers in the range $1$ to $n$ inclusive, with one integer missing — we need to find the missing integer. We are also told that we want to solve this using $O(n)$ time complexity and $O(1)$ space complexity. How could we do this?
We need to process at least $n$ numbers, but we cannot store these numbers because we want $O(1)$ space. This means we’d have to process the input as we go so that we aren’t using extra space.
Recall that the sum of all integers from $1$ to $n$ can be given by the following expression:
$$ \sum_{i=1}^{n} = \frac{n(n+1)}{2} $$
For example, the sum of all integers between $1$ and $5$ is:
$$ \sum_{i=1}^{5} = \frac{5(5+1)}{2} = 15 $$
Using this knowledge, we can find the missing integer by adding up all numbers in the input, then subtracting it from the sum of all integers $1$ to $n$.
In this problem, we need to be able to access the highest priority print job throughout numerous insertions and removals. This is great use case for a priority queue (PQ), however, we need to access the oldest job first if there are ties in the priority, and a PQ won’t do this by default.
To do this, we need to add some time field to the PQ records. We can either add a time field that represents the index of the job and make a custom comparator for the PQ to use the smallest time if the priority is tied (it would use the max otherwise); or we can initially set time to some really big value and count down over time. This way, when we pop from the priority queue we will see the intended behaviour of highest priority first — or, if a tie — the oldest inserted job.
Another piece of slight complexity is determining whether we should read an integer or the string print, as we cannot just take ints from the standard input (e.g., cin or input()) in the case that the input is the string “print”. We can always read a “print’ string to start with in each round, and if it is not “print”, we can convert it to an integer with stoi and read the other integer as usual.
This makes for an $O(n\log n)$ time complexity due to the priority queue operations, and up to $O(n)$ space.