Cost to convert one integer array into another This question is distilled from an interview question.
Given two arrays $a$ and $b$ containing $n$ integers each, change each integer in array $a$ into the corresponding integer in array $b$ by increasing or decreasing a single digit by $1$. What is the optimum algorithm?
The number of digits in $a[i]$ are the same as $b[i]$ and the length of arrays $a$ and $b$ are also the same.
An example, $a = [123, 456]$, $b= [124, 307]$. Then the minimum cost to convert array $a$ into array $b$ is 8.
I know of a naive solution to this question which of course is to count the number of increments to each digit but I'm wondering if there is a more efficient binary operation that can be used.
Let $\ell_{i}$ denote the number of digits in $a[i]$. Then the complexity of the naive algorithm as suggested by you is $O(\ell)$, where $\ell = \sum_{i = 1}^{n} \ell_{i}$.
Moreover, the algorithm must visit every digit at least once. For the sake of contradiction, suppose the algorithm did not visit some digit in the array. Then an adversary can modify the unvisited digit to a different digit. This will prove that your algorithm's output is incorrect. Therefore, any correct algorithm must require at least $\Omega(\ell)$  comparisons. Thus, you can not expect better than $\Theta(\ell)$ complexity for this problem.