Contest Duration: - (local time) (100 minutes) Back to Home
Official

## B - Count Distinct Integers Editorial by en_translator

### 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)


posted:
last update: