0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – greybeard
    Apr 24 at 3:54
  • $\begingroup$ 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. $\endgroup$
    – TWhite
    Apr 24 at 12:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – greybeard
    Apr 24 at 13:58
  • 1
    $\begingroup$ 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? $\endgroup$
    – TWhite
    Apr 25 at 0:42
  • $\begingroup$ 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. $\endgroup$
    – TWhite
    Apr 25 at 12:28
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – TWhite
    May 4 at 4:00
  • $\begingroup$ @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. $\endgroup$ May 4 at 11:58
  • $\begingroup$ @TWhite Such kind of proofs are known as adversarial lower bound proofs. For example see this: web.cs.ucdavis.edu/~amenta/w04/dis2.pdf $\endgroup$ May 4 at 11:58
  • $\begingroup$ @TWhite Yes, the algorithm must visit each digit at least once even if we transform the digit into another representation say binary or hexa etc. Since every digit is represented in binary form in a computer, visiting each digit means visiting every binary digit of that representation. $\endgroup$ May 4 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.