Xây dựng hàm G(Num): số lượng các số thuộc [0,Num] thỏa mãn đề bài.

Ta coi Num là 1 xâu độ dài n, có biểu diễn thập phân là ~t_0 t_1…t_{(n-2)} t_{(n-1)}~

Cấu hình nghiệm: ~X= x_0 x_1… x_{(n-2)} x_{(n-1)}~ với với x_i∈[0,9]

Ta sẽ xây dựng X bằng cách xây dựng từng thành phần ~x_i~ của nó theo thứ tự từ trái qua phải.

Trạng thái QHĐ của chúng ta sẽ là (id,cnt,smaller,nonz), trong đó:

• id là vị trí chữ số ta đang xây dựng
• cnt: Số lượng chữ số d xuất hiện trong phần nghiệm đã xây dựng X[0..id-1]
• smaller:

smaller=1: phần nghiệm đã xây dựng X[0..id-1] < Num[0..id-1]

smaller=0: phần nghiệm đã xây dựng X[0..id-1] = Num[0..id-1]

• nonz: Cho biết tính đến vị trí id-1 số X đã có nghĩa hay chưa (hay chỉ chứa toàn số 0). Quy ước = 1: đã có nghĩa, = 0: chỉ chứa toàn 0