One element that differs in two arrays. How to find it efficiently? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-17T19:50:45Z https://cs.stackexchange.com/feeds/question/67499 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/67499 21 One element that differs in two arrays. How to find it efficiently? Konstantino Sparakis https://cs.stackexchange.com/users/63162 2016-12-16T07:41:00Z 2016-12-19T15:02:15Z <p>I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem.</p> <p>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:</p> <p>Array 1 [78,11, 143, 84, 77, 1, 26, 35 .... n]</p> <p>Array 2 [11,84, 35, 25, 77, 78, 26, 143 ... <strong>21</strong>... n+1]</p> <p>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.</p> <p>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? </p> https://cs.stackexchange.com/questions/67499/-/67502#67502 15 Answer by Tobi Alafin for One element that differs in two arrays. How to find it efficiently? Tobi Alafin https://cs.stackexchange.com/users/62509 2016-12-16T08:50:13Z 2016-12-16T18:21:25Z <p>Element = Sum(Array2) - Sum(Array1)</p> <p>I <strong><em>sincerely</em></strong> 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.</p> <p>If the number of added elements is more than one, this won't work.</p> <p>My answer has the same run time complexity for best, worst, and average case,</p> <p><strong><em>EDIT</em></strong><br> After some thinking, I think my answer is your solution.</p> <p>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.</p> <p>We now have $2n-1$ operations. Sum$2 -$Sum$1 = 1$ operation.</p> <p>$2n - 1 + 1 = 2n$ operations.</p> <p>Worst case complexity of my algorithm: $$\Theta(n)$$</p> <p><strong><em>EDIT:</em></strong><br> Due to some problems with Data types, an XOR sum <a href="https://cs.stackexchange.com/questions/67499/one-element-that-differs-in-two-arrays-how-to-find-it-efficiently/67521#63227">as suggested by <em>reffu</em></a> will be more apt.</p> https://cs.stackexchange.com/questions/67499/-/67503#67503 31 Answer by Mario Cervera for One element that differs in two arrays. How to find it efficiently? Mario Cervera https://cs.stackexchange.com/users/57681 2016-12-16T09:07:50Z 2016-12-19T15:02:15Z <p>I see four main ways to solve this problem, with different running times:</p> <ul> <li><p>$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.</p></li> <li><p>$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.</p></li> </ul> <p>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 <strong>hash table</strong>.</p> <ul> <li>$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).</li> </ul> <p>If you want upper-bound guarantees and the arrays are strictly composed of integers, the best solution is, probably, the one suggested by <a href="https://cs.stackexchange.com/questions/67499/one-element-that-differs-in-two-arrays-how-to-find-it-efficiently/67502#67502">Tobi Alafin</a> (even though this solution will not give you the index of the element that differs in the second array):</p> <ul> <li>$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 <a href="https://en.wikipedia.org/wiki/Bitwise_operation#XOR" rel="nofollow noreferrer">bitwise XOR operator</a>. This is thoroughly explained in <a href="https://cs.stackexchange.com/questions/67499/one-element-that-differs-in-two-arrays-how-to-find-it-efficiently/67531#67531">Ilmari Karonen's</a> answer. </li> </ul> <p>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)$.</p> https://cs.stackexchange.com/questions/67499/-/67508#67508 1 Answer by gnasher729 for One element that differs in two arrays. How to find it efficiently? gnasher729 https://cs.stackexchange.com/users/17408 2016-12-16T09:58:14Z 2016-12-16T17:21:12Z <p>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. </p> <p>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. </p> <p>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). </p> <p>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 <em>one</em> additional item. </p> https://cs.stackexchange.com/questions/67499/-/67521#67521 14 Answer by reffu for One element that differs in two arrays. How to find it efficiently? reffu https://cs.stackexchange.com/users/63227 2016-12-16T13:52:01Z 2016-12-16T13:52:01Z <p><em>I'd post this as a comment on Tobi's answer, but I don't have the reputation yet.</em></p> <p>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.</p> <p>Just calculate the xor-sum (i.e. x^x^x...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).</p> <p>This is still <strong><em>O(n)</em></strong> and avoids any issues with overflow.</p> https://cs.stackexchange.com/questions/67499/-/67531#67531 16 Answer by Ilmari Karonen for One element that differs in two arrays. How to find it efficiently? Ilmari Karonen https://cs.stackexchange.com/users/1324 2016-12-16T16:43:02Z 2016-12-16T18:48:11Z <p>The $\Theta(n)$ difference-of-sums solution proposed by <a href="https://cs.stackexchange.com/a/67502">Tobi</a> and <a href="https://cs.stackexchange.com/a/67503">Mario</a> can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is:</p> <ul> <li><em>total</em>, 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);</li> <li><em>associative</em>, such that $a \oplus (b \oplus c) = (a \oplus b) \oplus c$;</li> <li><em>commutative</em>, such that $a \oplus b = b \oplus a$; and</li> <li><em>cancellative</em>, 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.</li> </ul> <p>(If the type can only take a finite number of distinct values, these properties are sufficient to make it into an <a href="https://en.wikipedia.org/wiki/Abelian_group" rel="nofollow noreferrer">Abelian group</a>; even if not, it will at least be a <a href="https://en.wikipedia.org/wiki/Commutative_property" rel="nofollow noreferrer">commutative</a> <a href="https://en.wikipedia.org/wiki/Cancellative_semigroup" rel="nofollow noreferrer">cancellative semigroup</a>.)</p> <p>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).$$</p> <p>For example, if the values in the arrays are integers, then integer addition (or <a href="https://en.wikipedia.org/wiki/Modular_arithmetic" rel="nofollow noreferrer">modular addition</a> for finite-length integers types) can be used as the operator $\oplus$, with subtraction as the inverse operation $\ominus$. Alternatively, for <em>any</em> data type whose values can be represented as fixed-length bit strings, we can use <a href="https://en.wikipedia.org/wiki/Bitwise_operation#XOR" rel="nofollow noreferrer">bitwise XOR</a> as both $\oplus$ and $\ominus$.</p> <p>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.</p> <p>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 <em>can</em> 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).</p> <p>More generally, one method that would work for arbitrary bit strings would be to apply <a href="https://en.wikipedia.org/wiki/Padding_(cryptography)#Bit_padding" rel="nofollow noreferrer">one-bit padding</a>, 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 <a href="https://en.wikipedia.org/wiki/Prefix_code" rel="nofollow noreferrer">prefix code</a>, and prepend those to the strings. Other possible encodings exist as well.</p> <p>In fact, since <em>any</em> 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.</p> <p>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.</p> https://cs.stackexchange.com/questions/67499/-/67569#67569 -1 Answer by Craig Hardcastle for One element that differs in two arrays. How to find it efficiently? Craig Hardcastle https://cs.stackexchange.com/users/63287 2016-12-17T22:14:59Z 2016-12-17T22:14:59Z <p>var shortest, longest;</p> <p>Convert shortest to a map for quick referencing and the loop over the longest until the current value is not in the map.</p> <p>Something like this in javascript:</p> <p>if (arr1.length > arr2.length) { shortest = arr2; longest = arr1; } else { shortest = arr1; longest = arr2; }</p> <p>var map = shortest.reduce(function(obj, value) { obj[value] = true; return obj; }, {});</p> <p>var difference = longest.find(function(value) { return !!!map[value]; });</p> https://cs.stackexchange.com/questions/67499/-/67578#67578 -1 Answer by Sillymistake for One element that differs in two arrays. How to find it efficiently? Sillymistake https://cs.stackexchange.com/users/63295 2016-12-18T00:41:36Z 2016-12-18T00:41:36Z <p>O(N) solution in time complexity O(1) in terms of space complexity</p> <p>Problem statement: Assuming that array2 contains all the elements of the array1 plus one other element not present in array1.</p> <p>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</p>