Tóm tắt đề bài

Cho một dãy số nguyên dương $a_1$, $a_2$,..., $a_n$. Đếm số cặp chỉ số $(i,j)$ sao cho $a_i$ + $a_j$ là một số đặc biệt (số mà các chữ số đều giống nhau).

Lời giải

Trước hết, ta nhận xét rằng số lượng số đặc biệt không lớn (có tổng cộng 55 số đặc biệt có giá trị không vượt quá 2 × ${10}^6$). Từ nhận xét trên, ta có thể giải bài toán như sau:

Khởi tạo mảng $cnt$ với toàn bộ phần tử bằng 0 ($cnt[x]$ có ý nghĩa là số phần tử có giá trị bằng $x$). Duyệt qua các phần tử của mảng $a$. Với mỗi phần tử $a_i$:

• Duyệt qua từng số đặc biệt $x$, cộng thêm giá trị $cnt[x-a_i]$ vào đáp án.
• Tăng giá trị $cnt[a_i]$ thêm 1.

Độ phức tạp: $O(N)$ với $N$ là số phần tử của dãy.