Số Đặc Biệt

Nguồn: Bài tập nhập môn (câu hỏi của bạn đọc) Độ khó: Dễ Mảng đánh dấu Tách chữ số Hàm

Đề bài

SỐ ĐẶC BIỆT

Một số là số đặc biệt khi mà các chữ số trong nó không bị trùng lặp, ví dụ 123, 3127, 4897 là các số đặc biệt.

Nhập vào một số nguyên dương $n$, hãy kiểm tra xem $n$ có phải là số đặc biệt hay không. Trả về true nếu phải và ngược lại (trả về false).

Ví dụ:

• Với $n = 123$ thì checkSpecialNumber(n) = true.
• Với $n = 112$ thì checkSpecialNumber(n) = false.

Đề gốc yêu cầu viết hàm checkSpecialNumber(n) và không ghi giới hạn của $n$. Trong bài này mình viết thành chương trình hoàn chỉnh: đọc $n$ (số nguyên dương, mình cho tối đa $10^{18}$ để vừa kiểu long long), in ra true hoặc false.

Ví dụ 1 – input

123

Ví dụ 1 – output

true

Ví dụ 2 – input

112

Ví dụ 2 – output

false

Lời mở đầu

Bài tập này thực ra rất cơ bản, bạn đăng bài là một bạn mới học (beginner) nhờ mọi người hướng dẫn dễ hiểu. Trong bài đăng đó mình thấy có một số anh em đưa ra những cách giải quyết hơi rườm rà, trong khi bài này có thể giải quyết theo một cách rất đơn giản nếu đã học mảng 1 chiều. Mình chia sẻ lại lên đây để anh em cùng xem xét làm thử rồi tham khảo giải pháp của mình bên dưới nhé 😉.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ: 123 có 3 chữ số 1, 2, 3 khác nhau đôi một ⇒ true. Còn 112 có chữ số 1 xuất hiện 2 lần ⇒ false. Tương tự 3127 (3, 1, 2, 7) và 4897 (4, 8, 9, 7) đều không có chữ số nào lặp lại nên là số đặc biệt.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Tách chữ số vào mảng, so từng cặpCách 2Mảng đánh dấu check[0..9]

Cách 1Tách chữ số vào mảng rồi so từng cặp – O(d²)

Về việc tách từng chữ số của số ban đầu ra thì cái này quá đơn giản chắc các bạn đã biết: ta cứ liên tục % 10 để lấy từng chữ số từ phải qua trái rồi liên tục / 10 đến khi nào số ban đầu về 0 thì dừng. Ví dụ $n = 3127$: $3127 \bmod 10 = 7$, còn 312; $312 \bmod 10 = 2$, còn 31; $31 \bmod 10 = 1$, còn 3; $3 \bmod 10 = 3$, còn 0 ⇒ dừng. Ta lấy được các chữ số 7, 2, 1, 3.

Cách mà nhiều bạn nghĩ tới đầu tiên: cất hết các chữ số vào một mảng, rồi dùng 2 vòng lặp lồng nhau so sánh mọi cặp chữ số; gặp cặp nào bằng nhau thì trả về false, so hết mà không gặp thì trả về true. Cách này đúng, nhưng phải viết 2 vòng lặp và số phép so sánh tăng theo bình phương số chữ số $d$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;
bool checkSpecialNumber(long long n) {
    int digit[20];
    int cnt = 0;
    while (n != 0) {
        digit[cnt] = n % 10;
        cnt++;
        n /= 10;
    }
    for (int i = 0; i < cnt; i++) {
        for (int j = i + 1; j < cnt; j++) {
            if (digit[i] == digit[j]) {
                return false;
            }
        }
    }
    return true;
}
int main() {
    long long n;
    cin >> n;
    if (checkSpecialNumber(n) == true) {
        cout << "true";
    }
    else {
        cout << "false";
    }
    return 0;
}

def check_special_number(n):
    digit = []
    while n != 0:
        digit.append(n % 10)
        n //= 10
    cnt = len(digit)
    for i in range(cnt):
        for j in range(i + 1, cnt):
            if digit[i] == digit[j]:
                return False
    return True


n = int(input())
print("true" if check_special_number(n) else "false")

Đánh giá độ phức tạp của cách làm này: với $d$ là số chữ số của $n$ ($d \le 19$):

• Không gian: mảng $d$ chữ số – $O(d)$.
• Thời gian: tách chữ số $O(d)$ + so $\frac{d(d-1)}{2}$ cặp ⇒ $O(d^2)$.

Không gian$O(d)$

Thời gian$O(d^2)$

Cách 2Mảng đánh dấu check[0..9] – O(d)

Vấn đề là làm sao kiểm tra xem từng chữ số lấy ra đó có bị trùng với chữ số trước đó đã có chưa? Để giải quyết vấn đề này rất đơn giản nếu đã học mảng 1 chiều. Ta nhận thấy các chữ số của 1 số chỉ có thể trong đoạn từ 0 đến 9, vì thế ta tạo ra mảng đánh dấu, thống kê xem chữ số đó đã xuất hiện chưa. Mảng này có 10 phần tử để các index của mảng cũng từ 0 đến 9 luôn. Như thế thì giá trị check[i] chính là trả lời câu hỏi "chữ số $i$ đã xuất hiện chưa?" (với $i$ chạy từ 0 đến 9).

• Ban đầu khởi tạo toàn bộ mảng đều là false (nghĩa là tất cả các chữ số đều chưa xuất hiện).
• Với mỗi chữ số digit tách ra bằng cách % 10, ta gọi vào index tương ứng của nó trong mảng: nếu check[digit] đang là true (tức là chữ số này trước đó đã có) thì ta return false ngay.
• Còn nếu đang là false thì ta đánh dấu lại giờ đây nó là true (tức là đã xuất hiện) và cứ thế xét qua chữ số tiếp theo.
• Nếu đến sau cùng vẫn không có tình huống nào khiến return false thì ta return true – số thỏa mãn.

Ý chính

Thay vì so một chữ số với tất cả chữ số đã gặp, ta hỏi thẳng "ô check[digit] đã bật chưa?" – chỉ 1 phép truy cập mảng. Đây là kỹ thuật mảng đánh dấu dùng rất nhiều về sau (đếm phân phối, sàng nguyên tố...).

Minh hoạ mảng đánh dấu

Các bạn nhập $n$ rồi bấm Tiếp để xem từng chữ số được tách ra (từ phải qua trái) và mảng check thay đổi thế nào:

n (tối đa 18 chữ số)

Ví dụ nhanh:

Code cho các bạn tham khảo với tư tưởng mình vừa nói ở trên để dễ hình dung hơn (hàm checkSpecialNumber là của mình, phần main mình thêm vào để chạy thử):

#include <iostream>
using namespace std;
bool checkSpecialNumber(long long n) {
    bool check[10] = {false};
    while (n != 0) {
        int digit = n % 10;
        n /= 10;
        if (check[digit] == true) {
            return false;
        }
        else {
            check[digit] = true;
        }
    }
    return true;
}
int main() {
    long long n;
    cin >> n;
    if (checkSpecialNumber(n) == true) {
        cout << "true";
    }
    else {
        cout << "false";
    }
    return 0;
}

def check_special_number(n):
    check = [False] * 10
    while n != 0:
        digit = n % 10
        n //= 10
        if check[digit]:
            return False
        else:
            check[digit] = True
    return True


n = int(input())
print("true" if check_special_number(n) else "false")

Khung chạy tay:

C++▶ Chạy tay từng dòng codeCách 2: tách từng chữ số bằng % 10, / 10; check[digit] đã true thì trùng → false.

Dữ liệu vào (stdin) – sửa thoải mái123

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3bool checkSpecialNumber(long long n) {

4 bool check[10] = {false};

5 while (n != 0) {

6 int digit = n % 10;

7 n /= 10;

8 if (check[digit] == true) {

9 return false;

10 }

11 else {

12 check[digit] = true;

13 }

14 }

15 return true;

16}

17int main() {

18 long long n;

19 cin >> n;

20 if (checkSpecialNumber(n) == true) {

21 cout << "true";

22 }

23 else {

24 cout << "false";

25 }

26 return 0;

27}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng 10 phần tử – $O(1)$.
• Thời gian: mỗi chữ số chỉ tách 1 lần và tra mảng 1 lần ⇒ $O(d)$, với $d \le 19$ là tức thì.

Không gian$O(1)$

Thời gian$O(d)$

Một nhận xét thú vị

Chỉ có 10 chữ số từ 0 đến 9, nên số nào có từ 11 chữ số trở lên chắc chắn bị trùng (nguyên lý Dirichlet – 11 "con thỏ" nhốt vào 10 "chuồng"). Số đặc biệt lớn nhất là 9876543210. Code ở trên không cần xét riêng điều này vì gặp chữ số trùng là return false ngay, nên vòng while chạy tối đa 11 lần.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với mọi $n$ từ 1 đến 2999 và 2000 số ngẫu nhiên tới $10^{18}$ (thêm các số biên như 9876543210, 1023456789, $10^{18}$), so với cách kiểm tra bằng tập hợp các ký tự (len(set(str(n))) == len(str(n))) – khớp hết; 4 số của đề (123, 3127, 4897 → true; 112 → false) đều đúng.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇