فرض کنید مجموعه $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$ اشتراک دارد یا نه.