Chương trình đếm số đặc biệt trong khoảng cho trước trong Python

Số đặc biệt: số nguyên dương có 1 chữ số (1-9), hoặc số nhiều chữ số chia hết cho số chữ số và thương cũng là số đặc biệt. Đếm số đặc biệt trong [left_limit, right_limit].

Ví dụ

Input: left_limit=5, right_limit=30 → Output: 13

Các số đặc biệt: 5,6,7,8,9,10,12,14,16,18,20,24,28

Thuật toán sinh số đặc biệt

1. Nếu right_limit < 10: trả về right_limit - left_limit + 1
2. Khởi tạo danh sách number_list với các số đặc biệt biết trước: [0..9, 10,12,14,16,18]
3. Với mỗi độ dài j từ 2 đến độ dài right_limit:
   • Với mỗi k trong number_list: temp = k × j
   • Nếu len(str(temp)) == j → thêm vào number_list
   • Nếu len(str(temp)) > j → break (vì k tăng dần)
   • Nếu phần tử cuối ≥ right_limit → break
4. Loại trùng, sắp xếp, đếm số trong khoảng

Mã nguồn

def strange(left_limit, right_limit):
    if right_limit < 10:
        return right_limit - left_limit + 1
    len_right = len(str(right_limit))
    number_list = [0,1,2,3,4,5,6,7,8,9,10,12,14,16,18]
    for j in range(2, len_right + 1):
        for k in number_list:
            temp1 = k * j
            if len(str(temp1)) == j:
                number_list.append(temp1)
            elif len(str(temp1)) > j:
                break
            if number_list[-1] >= right_limit:
                break
    number_list = list(set(number_list))
    count = 0
    for temp2 in number_list:
        if left_limit <= temp2 <= right_limit:
            count += 1
    return count

print(strange(5, 30))  # Output: 13

Giải thích tính chất số đặc biệt

Định nghĩa đệ quy: x đặc biệt ⟺ x % len(str(x)) == 0 và x / len(str(x)) đặc biệt.

Ví dụ: 28 có 2 chữ số, 28%2=0, 28/2=14. 14 có 2 chữ số, 14%2=0, 14/2=7. 7 có 1 chữ số → đặc biệt.

Thuật toán sinh tất cả số đặc biệt ≤ right_limit bằng cách nhân các số đã biết với độ dài chữ số.