Solution 1

Inspect each integer appearing in \(a\) in order, and “add \(1\) to the answer if it is the first occurrence.”

\(a_i\) is the first occurrence of the integer if \(a_j \neq a_i\) for all \(j < i\). We can get accepted by implementing this with a for statement.

The worst complexity is \(\Theta (N^2)\).

Sample code (C++):

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int& x : a) {
    cin >> x;
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    bool appeared = false;
    for (int j = 0; j < i; ++j) {
      if (a[i] == a[j]) {
        appeared = true;
      }
    }
    if (!appeared) {
      ans += 1;
    }
  }
  cout << ans << '\n';
}

Sample code (Python):

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
  appeared = False;
  for j in range(i):
    if a[i] == a[j]:
      appeared = True
  if not appeared:
    ans += 1
print(ans)

Solution 2

The problem can be solved with a data structure that manages a set (without duplicates). In C++, we can use std::set; in Python, we can use set. For more details on how to use, please refer to the official references (C++, Python).

The worst complexity is \(\Theta (N \log N)\).

Sample code (C++):

#include <iostream>
#include <set>
using namespace std;

int main() {
  int n;
  cin >> n;
  set<int> a;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    a.insert(x);
  }
  cout << a.size() << '\n';
}

Sample code (Python):

n = int(input())
print(len(set(map(int, input().split()))))

Solution 3

After sorting \(a\) in the increasing order, equal elements sits side by side. The answer is the number of \(i\) such that \(a_i \neq a_{i + 1}\) in the sorted array, plus \(1\).

The worst complexity is \(\Theta (N \log N)\).

Sample code (C++):

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int& x : a) {
    cin >> x;
  }
  sort(begin(a), end(a));
  int ans = 1;
  for (int i = 0; i < n - 1; ++i) {
    if (a[i] != a[i + 1]) {
      ans += 1;
    }
  }
  cout << ans << '\n';
}

Sample code (Python) :

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 1
for i in range(n - 1):
  if a[i] != a[i + 1]:
    ans += 1
print(ans)