Nhìn vào bài toán, ta có thể nghĩ ngay tới quy hoạch động chữ số, một trong những thuật toán quy hoạch động cổ điển. Tuy nhiên, vì giới hạn ~n~ tương đối lớn, ta cần tìm cách tối ưu hơn.

Nhận xét quan trọng: Ta thấy được, nếu ~(n\ mod\ 10^{11})~ chia hết cho ~2048~ (hay nói cách khác, ~11~ chữ số cuối cùng của ~n~ chia hết cho ~2048~) thì ~n~ cũng chia hết cho ~2048~ (chứng minh dễ, xin nhường lại cho bạn đọc).

Vì vậy, ta chỉ cần quy hoạch động trên ~11~ chữ số cuối cùng của ~n~, còn các ký tự ~\texttt{?}~ ngoài ~11~ ký tự cuối có thể điền chữ số bất kỳ.

Độ phức tạp: ~O((n - 11) + 11 \cdot 2048)~ = ~O(n)~.