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\dots t_{(n-2)}{t}_{(n-1)}$

Cấu hình nghiệm: $X=x_0{x}_1\dots 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