Số có bạn - LCOJ: Luyện Code Online Judge

FRIENUM - Số có bạn

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho số nguyên dương ~n~ và dãy ~n~ số nguyên dương ~a_1, a_2, …, a_n~. Ta gọi một số ~a_i~ là có bạn nếu ~∃j ≠ i ,a_i = a_j~. Hãy đếm số lượng số có bạn trong dãy số trên.

Input

Dòng đầu ghi số nguyên dương ~n~.
Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, …, a_n~. Hai số liên tiếp được ghi cách nhau một dấu cách.

Giới hạn:

~80\%~ số điểm có ~n ≤ 10^3~ và ~1 ≤ a_i ≤ 10^6~;
~20\%~ số điểm có ~10^3 < n ≤ 10^6~ và ~1 ≤ a_i ≤ 10^6~.

Output

Một dòng duy nhất ghi số nguyên là số lượng số có bạn tìm được.

Sample

Input #1

6
1 2 2 3 1 2

Output #1

Hint

Xét #1:

Có ~5~ số có bạn bao gồm hai số ~1~ và ba số ~2~.

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

include <bits/stdc++.h>

using namespace std; int main(){ ios::syncwithstdio(false); cin.tie(NULL);

int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++){
    cin >> a[i];
}
const int MAXV = 1000000;
vector<int> cnt(MAXV+1, 0);
for(int x: a){
    cnt[x]++;
}
long long ans = 0;
for(int x: a){
    if(cnt[x] >= 2) ans++;
}
cout << ans;
return 0;

}