Game (Editorial)

We will simulate the game using a data structure — a set. The set will store all the numbers currently written on the paper.

Each time Fidan says a number, Fuad checks whether it is in the set:

• if it is — he removes the number from the set (erases it from the paper);

• if it is not — he adds the number to the set (writes it on the paper).

The number of elements remaining on the paper at the end of the game is equal to the number of elements in the set.

Example

Let’s simulate how the set behaves for the first and second examples.

At the end of the game:

• The first set contains $2$ elements;

• The second set is empty (contains $0$ elements).

Algorithm implementation

Read the number of elements $n$.

scanf("%d", &n);

Process the $n$ numbers said by Fidan one by one.

for (i = 0; i < n; i++)
{
  scanf("%d", &x);

Each time Fidan says a number $x$:

• If the number $x$ is not in the set, we add it.

• If the number $x$ is already in the set, we remove it.

  if (s.find(x) == s.end())
    s.insert(x);
  else
    s.erase(x);
}

Print the answer — the size of the set $s$.

printf("%d\n", s.size());

Python implementation

Read the input data.

n = int(input())
lst = map(int,input().split())

Declare a set.

s = set()

Process the numbers said by Fidan one by one.

for x in lst:

Each time Fidan says a number $x$:

• If the number $x$ is already in the set, we remove it.

• If the number $x$ is not in the set, we add it.

  if x in s:
    s.remove(x)
  else:
    s.add(x)

Print the answer — the size of the set $s$.

print(len(s))