‎ فرض کنید مجموعه ‎$K$‎ از بازه های مجزای ‎$[a_2,b_2]$‎ ، ‎$[a_1,b_1]$‎ تا ‎$[a_n,b_n]$‎ تشکیل شده باشد و ‎$b_i < a_{i+1}$‎.

فرض کنید تابع ‎$g(x,y,t)$‎ برابر باشد با کم‌ترین ‎$p$‎ که ‎$p > t$‎ و ‎$f_{x,y}(p) \in K$.

می‌توان نشان داد که شرط لازم و کافی برای این که ‎$x$‎ و$y$ k-equivalent باشند این است که شرایط زیر بر قرار باشد. ‎‎

• $g(x,y,0) = a_1$‎
• ‎ $g(x,y,b_i) = a_{i+1},i < n$‎
• $g(x,y,b_n) = \infty$‎

‎ پس اگر ما بتوانیم تابع ‎$g$‎ را پیاده سازی کنیم می‌توانیم پاسخ سوال را به‌دست آوریم‎.

‎ برای این کار می‌توانیم سمت چپ‌ترین رقمی از ‎$g(x,y,t)$‎ که با ‎$t$‎ تفاوت دارد را محاسبه کنیم و آن را تصحیح کنیم و به جای ارقام سمت راست آن ‎0‎ قرار دهیم عدد ‎($q(t)$)‎. در صورتی که عدد به‌دست آمده عضوی از ‎$K$‎ باشد، عدد به‌دست آمده همان جواب است، در غیر این صورت مقدار ‎$g(x,y,q(t))$‎ را به عنوان جواب بر می‌گردانیم. چون در هر مرحله یکی از ارقام عدد معلوم می شود، حد اکثر پس از ‎$18$‎ مرحله جواب مشخص می شود‎.

‎ برای به دست آوردن ‎$q(t)$‎ باید به ازای تمامی ارقام ‎$t$ (شامل صفر‌های بی‌ارزش آن) مقادیر بیش‌تر را قرار دهیم و ارقام سمت راست را برابر با ? قرار دهیم. ‎$f_{x,y}$‎ عدد به‌دست آمده یک بازه را تشکیل می‌دهد، در صورتی که این بازه با ‎$K$‎ اشتراک داشت آن را به عنوان جواب برمی‌گردانیم، در غیر این صورت به سراغ ارقام بعدی‌می رویم‎.

حال به ازای تمام ‎$a$‎ و ‎$b$‎ های بین ‎$1$‎ تا ‎$9$‎ شرایط را چک می‌کنیم و رده‌های ‎k-equivalent‎ را به‌دست می‌آوریم‎.‎ ‎

پيچيدگي

چون هر کدام از اعداد ورودی حداکثر ‎$18$‎ رقم دارند، تمام اعمال گفته شده از ‎$o(1)$‎ می‌باشد، به غیر از چک کردن این که‌ یک بازه با ‎$K$‎ اشتراک دارد یا نه. اگر تمام ‎$a_i$‎ ها و ‎$b_i$‎ ها را به صورت مرتب داشته باشیم، با استفاده از‎binary search‎ می‌توانیم در زمان ‎$o(\log{n})$‎ چک کنیم که آیا یک بازه ‎$[a',b']$‎ با$K$‎ اشتراک دارد یا نه.