Đặt:

• ~pre_i~ là phần dư của tổng các chữ số từ ~1~ đến ~i~ của ~N~ khi chia cho ~3~.

• ~d~ là phần dư của tổng các chữ số của ~N~ khi chia cho ~3~.

Ta thấy rằng khi xóa đoạn ~[L, R]~, để số mới chia hết cho ~3~ thì phần dư tổng các chữ số trong đoạn ~[L, R]~ phải bằng ~d~. Duyệt qua ~R~, tìm được ~L~ thỏa mãn khi ~pre_R - pre_{L-1} \equiv d \pmod{3}~ hay ~pre_{L-1} \equiv pre_R - d \pmod{3}~. Để đếm được số vị trí ~L~, duy trì một mảng đếm số các phần tử ~pre_i~ chia ~3~ dư ~0, 1, 2~.

Độ phức tạp: ~\mathcal{O}(N)~.