# 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.

• What is the correspondence between integers and digits? If integers were represented by a sign and positive digits from 0 to 5, would there be a "borrow" decrementing a zero, a carry incrementing a 5? What significance do the arrays have? Apr 24 at 3:54
• The integers are composed of digits. For example, the integer 123 has three digits: 1,2, and 3. Not sure what you mean by a carry incrementing a 5? Is this a base 6 system with a sign? The arrays are part of the problem, there's no special significance. Apr 24 at 12:56
• The arrays are part of the problem If part of your question post is a quote of a problem from a third party, please a) use a block quote, and 1) properly attribute and credit. Apr 24 at 13:58
• The question is a distillation of a programming puzzle from an interview. I have stripped away a lot of the extraneous details. How should I attribute that? Apr 25 at 0:42
• Have updated the question. There is 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. Apr 25 at 12:28

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.
• Very interesting answer. Do you mind clarifying the complexity notation? What do $\Omega$ and $\Theta$ mean? Also the critical assumption here is each digit must be visited once? Is this true? Intuitively yes, but I haven't convinced myself that it is so. Your argument via an adversarial attack certainly is compelling. But what if I transformed the digits into another representation, would the argument still hold? May 4 at 4:00
• @TWhite $O$ is an asymptotic notation for upper bounds. $\Omega$ is an asymptotic notation for lower bounds. $\Theta$ notation is for tight bounds. In other words, $\Theta$ means both $O$ and $\Omega$. There are many online resources for the same: www2.cs.arizona.edu/classes/cs345/summer14/files/bigO.pdf and en.wikipedia.org/wiki/…. These are basic terms that we regularly use to analyse the running time of the algorithms. May 4 at 11:58