21
$\begingroup$

I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem.

Let's say we have two arrays consisting of numbers that are unsorted. Array 2 contains a number that Array 1 does not. Both arrays have randomly located numbers, not necessarily in the same order or at the same indices. For example:

Array 1 [78,11, 143, 84, 77, 1, 26, 35 .... n]

Array 2 [11,84, 35, 25, 77, 78, 26, 143 ... 21... n+1]

What is the fastest algorithm for finding the number that differs? What is its running time? In this example, the number we would be looking for is 21.

My idea was to run through Array 1 and delete that value from array 2. Iterate until you are finished. This should be around $O(n \log n)$ running time, right?

$\endgroup$
  • $\begingroup$ @Jandvorak Thank you guys for the responses. I was up late and happened to fall asleep after posting this. The array is unsorted, and all Items appear at random indexs in both arrays. $\endgroup$ – Konstantino Sparakis Dec 16 '16 at 10:11
  • $\begingroup$ @KonstantinoSparakis: this clarification invalidates the answers that assume that both arrays contain the elements in the same positions. $\endgroup$ – Mario Cervera Dec 16 '16 at 10:25
  • $\begingroup$ Cross posting is frowned upon softwareengineering.stackexchange.com/users/256931/… $\endgroup$ – paparazzo Dec 17 '16 at 0:08
  • $\begingroup$ @Paparazzi Was simply looking for a solution I read in the meta software engineering was where to go to get a solution but at the time I didn't know about the CS forum. I have notified the mods, to clean it up. $\endgroup$ – Konstantino Sparakis Dec 17 '16 at 0:25
  • $\begingroup$ @Paparazzi is there a meta post backing that up? I personally don't see any way to implement that policy well. $\endgroup$ – djechlin Dec 18 '16 at 2:06
31
$\begingroup$

I see four main ways to solve this problem, with different running times:

  • $O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes linear time. You carry out $n$ deletions; therefore, this algorithm takes quadratic time.

  • $O(n \: log \: n)$ solution: sort the arrays beforehand; then, perform a linear search to identify the distinct element. In this solution, the running time is dominated by the sorting operation, hence the $O(n \: log \: n)$ upper bound.

When you identify a solution to a problem, you should always ask yourself: can I do better? In this case, you can, making a clever use of data structures. Note that all you need to do is to iterate one array and perform repeated lookups in the other array. What data structure allows you to do lookups in (expected) constant time? You guessed right: a hash table.

  • $O(n)$ solution (expected): iterate the first array and store the elements in a hash table; then, perform a linear scan in the second array, looking up each element in the hash table. Return the element that is not found in the hash table. This linear-time solution works for any type of element that you can pass to a hash function (e.g., it would work similarly for arrays of strings).

If you want upper-bound guarantees and the arrays are strictly composed of integers, the best solution is, probably, the one suggested by Tobi Alafin (even though this solution will not give you the index of the element that differs in the second array):

  • $O(n)$ solution (guaranteed): sum up the elements of the first array. Then, sum up the elements of the second array. Finally, perform the substraction. Note that this solution can actually be generalized to any data type whose values can be represented as fixed-length bit strings, thanks to the bitwise XOR operator. This is thoroughly explained in Ilmari Karonen's answer.

Finally, another possibility (under the same assumption of integer arrays) would be to use a linear-time sorting algortihm such as counting sort. This would reduce the running time of the sorting-based solution from $O(n \: log \: n)$ to $O(n)$.

$\endgroup$
  • 4
    $\begingroup$ summing isn't linear if numbers get large enough, though. $\endgroup$ – Sarge Borsch Dec 16 '16 at 15:40
  • 9
    $\begingroup$ One nice thing about the summing algorithm is that it works with any abelian group, not just with integers (Most notably, uint64; cc @sarge). $\endgroup$ – John Dvorak Dec 16 '16 at 16:14
  • 6
    $\begingroup$ @Abdul the thing is if your integers are very large, you can no longer pretend they take $O(n)$ to add. I believe the complexity grows to $O(n \ln n)$ if you account for that. Using XOR instead of ordinary addition solves that, though, while still allowing for arbitrarily large number in input. $\endgroup$ – John Dvorak Dec 16 '16 at 16:49
  • 2
    $\begingroup$ @JanDvorak No, it doesn't. You're assuming the operation defined on the abelian group takes constant time. That cannot just be assumed. $\endgroup$ – UTF-8 Dec 17 '16 at 9:51
  • 2
    $\begingroup$ @UTF-8 I'm not assuming that. But it does so in finite groups (uint64), and in-place digit-wise addition (addition in ${Z_n}^d$) is linear in size of the out-of-place operand. So, computing the sum in such groups is linear-time in the total size of the operands. $\endgroup$ – John Dvorak Dec 17 '16 at 10:03
16
$\begingroup$

The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is:

  • total, such that for any values $a$ and $b$, $a \oplus b$ is defined and of the same type (or at least of some appropriate supertype of it, for which the operator $\oplus$ is still defined);
  • associative, such that $a \oplus (b \oplus c) = (a \oplus b) \oplus c$;
  • commutative, such that $a \oplus b = b \oplus a$; and
  • cancellative, such that there exists an inverse operator $\ominus$ that satisfies $(a \oplus b) \ominus b = a$. Technically, this inverse operation doesn't even necessarily have to be constant-time, as long as "subtracting" two sums of $n$ elements each doesn't take more than ${\rm O}(n)$ time.

(If the type can only take a finite number of distinct values, these properties are sufficient to make it into an Abelian group; even if not, it will at least be a commutative cancellative semigroup.)

Using such an operation $\oplus$, we can define the "sum" of an array $a = (a_1, a_2, \dots, a_n)$ as $$(\oplus\, a) = a_1 \oplus a_2 \oplus \dotsb \oplus a_n.$$ Given another array $b = (b_1, b_2, \dots, b_n, b_{n+1})$ containing all the elements of $a$ plus one extra element $x$, we thus have $(\oplus\, b) = (\oplus\, a) \oplus x$, and so we can find this extra element by computing: $$x = (\oplus\, b) \ominus (\oplus\, a).$$

For example, if the values in the arrays are integers, then integer addition (or modular addition for finite-length integers types) can be used as the operator $\oplus$, with subtraction as the inverse operation $\ominus$. Alternatively, for any data type whose values can be represented as fixed-length bit strings, we can use bitwise XOR as both $\oplus$ and $\ominus$.

More generally, we can even apply the bitwise XOR method to strings of variable length, by padding them up to the same length as necessary, as long as we have some way to reversibly remove the padding at the end.

In some cases, this is trivial. For example, C-style null terminated byte strings implicitly encode their own length, so applying this method for them is trivial: when XORing two strings, pad the shorter one with null bytes to make their length match, and trim any extra trailing nulls from the final result. Note that the intermediate XOR-sum strings can contain null bytes, though, so you'll need to store their length explicitly (but you'll only need one or two of them at most).

More generally, one method that would work for arbitrary bit strings would be to apply one-bit padding, where each input bitstring is padded with a single $1$ bit and then with as many $0$ bits as necessary to match the (padded) length of the longest input string. (Of course, this padding does not need to be done explicitly in advance; we can just apply it as needed while computing the XOR sum.) At the end, we simply need to strip any trailing $0$ bits and the final $1$ bit from the result. Alternatively, if we knew that the strings were e.g. at most $2^{32}$ bytes long, we could encode the length of each string as a 32-bit integer and prepend it to the string. Or we could even encode arbitrary string lengths using some prefix code, and prepend those to the strings. Other possible encodings exist as well.

In fact, since any data type representable on a computer can, by definition, be represented as a finite-length bit string, this method yields a generic $\Theta(n)$ solution to the problem.

The only potentially tricky part is that, for the cancellation to work, we need to choose a unique canonical bitstring representation for each value, which could be difficult (indeed, potentially even computationally undecidable) if the input values in the two arrays may be given in different equivalent representations. This is not a specific weakness of this method, however; any other method of solving this problem can also be made to fail if the input is allowed to contain values whose equivalence is undecidable.

$\endgroup$
  • $\begingroup$ Wow very interesting take on this. Thank you @IlmariKaronen $\endgroup$ – Konstantino Sparakis Dec 17 '16 at 0:19
15
$\begingroup$

Element = Sum(Array2) - Sum(Array1)

I sincerely doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps.

If the number of added elements is more than one, this won't work.

My answer has the same run time complexity for best, worst, and average case,

EDIT
After some thinking, I think my answer is your solution.

For an array of length $n$, number of primitive operation to find sum = $n-1$ Sum of Array$1 = n-1$ operations. Sum of Array$2 = n+1 -1=n$ operations.

We now have $2n-1$ operations. Sum$2 - $Sum$1 = 1 $ operation.

$2n - 1 + 1 = 2n$ operations.

Worst case complexity of my algorithm: $$\Theta(n)$$

EDIT:
Due to some problems with Data types, an XOR sum as suggested by reffu will be more apt.

$\endgroup$
  • $\begingroup$ Note that this method may not yield an accurate answer if your values are floats, since summing up the numbers might introduce roundoff errors. It will work for integer values, though, provided that either a) your integer type has well defined wrap-around behavior on overflow, or b) you store the sums in variables of a type wide enough that they cannot overflow. $\endgroup$ – Ilmari Karonen Dec 16 '16 at 15:10
  • $\begingroup$ Ruby's "BigNum" class can likely handle this. $\endgroup$ – Tobi Alafin Dec 16 '16 at 17:07
  • $\begingroup$ It absolutely doesn't work if your array contains for example strings, or just about anything that cannot be meaningfully added. $\endgroup$ – gnasher729 Dec 16 '16 at 17:23
  • $\begingroup$ Yup, I realised. What about using 'XOR'? Will it work for floats? $\endgroup$ – Tobi Alafin Dec 16 '16 at 17:31
  • $\begingroup$ Yes and also pointers and in general anything that consists of a fixed number bits. Many languages don't support that, but that's not a fundamental problem. Modular addition/subtraction will work in the same cases. $\endgroup$ – harold Dec 16 '16 at 17:37
14
$\begingroup$

I'd post this as a comment on Tobi's answer, but I don't have the reputation yet.

As an alternative to calculating the sum of each list (especially if they are large lists or contain very large numbers that might overflow your data type when summed) you can use xor instead.

Just calculate the xor-sum (i.e. x[0]^x[1]^x[2]...x[n]) of each list and then xor those two values. This will give you the value of the extraneous item (but not the index).

This is still O(n) and avoids any issues with overflow.

$\endgroup$
  • 3
    $\begingroup$ I'd also use XOR, because it seems a bit neater, but to be fair, overflow isn't really an issue as long as the language you're implementing this in supports overflow by wrapping. $\endgroup$ – Martin Ender Dec 16 '16 at 14:32
1
$\begingroup$

Assuming that array 2 was created by taking array 1 and inserting an element at a random position, or array 1 was created by taking array 2 and deleting a random element.

If all the array element are guaranteed to be distinct, the time is O (ln n). You compare the elements at location n/2. If they are equal, the extra element is from n/2 + 1 to the end of the array, otherwise it is from 0 to n/2. And so on.

If the array elements are not guaranteed to be distinct: You could have n times the number 1 in array 1, and the number 2 inserted anywhere in array 2. In that case you can't know where the number 2 is without looking at all array elements. Therefore O (n).

PS. Since the requirements changed, check your library for what is available. On macOS / iOS, you create an NSCountedSet, add all numbers from array 2, remove all numbers from array 1, and what's left is everything that is in array 2 but not in array 1, without relying on the claim that there is one additional item.

$\endgroup$
  • $\begingroup$ This answer was spot-on, but the question has been edited with a new requirement that invalidates your assumption. $\endgroup$ – Mario Cervera Dec 16 '16 at 10:33
  • $\begingroup$ Your new answer seems right. What's the Time complexity. $\endgroup$ – Tobi Alafin Dec 16 '16 at 17:42
  • $\begingroup$ Well, first what is the time needed to write the code. It's trivial. NSCountedSet uses hashing, so time complexity is "usually linear". $\endgroup$ – gnasher729 Dec 18 '16 at 11:31
-1
$\begingroup$

var shortest, longest;

Convert shortest to a map for quick referencing and the loop over the longest until the current value is not in the map.

Something like this in javascript:

if (arr1.length > arr2.length) { shortest = arr2; longest = arr1; } else { shortest = arr1; longest = arr2; }

var map = shortest.reduce(function(obj, value) { obj[value] = true; return obj; }, {});

var difference = longest.find(function(value) { return !!!map[value]; });

$\endgroup$
  • $\begingroup$ Codes without explanation does not count as a good answer here. Also why would you use !!! ? $\endgroup$ – Evil Dec 17 '16 at 22:56
-1
$\begingroup$

O(N) solution in time complexity O(1) in terms of space complexity

Problem statement: Assuming that array2 contains all the elements of the array1 plus one other element not present in array1.

The solution is : We use xor to find the element which is not present in array1 so steps are: 1. Start from array1 and do xor of all the elements and store them in a variable. 2. Take the array2 and do the xor of all elements with the variable which store the xor of array1. 3. After doing the operation our variable will contain the element which is present only in array2. The above algorithm works because of the following property of xor " a xor a =0" "a xor 0=a" I hope this solves your problem . Also the above suggested solutions are also fine

$\endgroup$

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.