Menu
Assume that the array has integers between 1 and 1,000,000.
I know some popular ways of solving this problem:
I recently came across another solution and I need some help in understanding the logic behind it:
Keep a single radix accumulator. You exclusive-or the accumulator with both the index and the value at that index.
The fact that x ^ C ^ x == C is useful here, since each number will be xor'd twice, except the one that's in there twice, which will appear 3 times. (x ^ x ^ x == x) And the final index, which will appear once. So if we seed the accumulator with the final index, the accumulator's final value will be the number that is in the list twice.
I will appreciate it if some one can help me understand the logic behind this approach (with a small example!).
784
Multiply the array element at that given value (index) with a negative number say -1. If a number have appeared once then the value in the array at that index will be negative else it will be positive if it has appeared twice (-1 * -1 = 1).
If you need the index of the found element in the array, use findIndex() . If you need to find the index of a value, use indexOf() .
To get the second to last element in an array, call the at() method on the array, passing it -2 as a parameter, e.g. arr.at(-2) . The at method returns the array element at the specified index.
To check if all values in an array are equal:Use the Array. every() method to iterate over the array. Check if each array element is equal to the first one. The every method only returns true if the condition is met for all array elements.
Assume you have an accumulator
int accumulator = 0;
At each step of your loop, you XOR the accumulator with i and v, where i is the index of the loop iteration and v is the value in the ith position of the array.
accumulator ^= (i ^ v)
Normally, i and v will be the same number so you will end up doing
accumulator ^= (i ^ i)
But i ^ i == 0, so this will end up being a no-op and the value of the accumulator will be left untouched. At this point I should say that the order of the numbers in the array does not matter because XOR is commutative, so even if the array is shuffled to begin with the result at the end should still be 0 (the initial value of the accumulator).
Now what if a number occurs twice in the array? Obviously, this number will appear three times in the XORing (one for the index equal to the number, one for the normal appearance of the number, and one for the extra appearance). Furthermore, one of the other numbers will only appear once (only for its index).
This solution now proceeds to assume that the number that only appears once is equal to the last index of the array, or in other words: that the range of numbers in the array is contiguous and starting from the first index to be processed (edit: thanks to caf for this heads-up comment, this is what I had in mind really but I totally messed it up when writing). With this (N appears only once) as a given, consider that starting with
int accumulator = N;
effectively makes N again appear twice in the XORing. At this point, we are left with numbers that only appear exactly twice, and just the one number that appears three times. Since the twice-appearing numbers will XOR out to 0, the final value of the accumulator will be equal to the number that appears three times (i.e. one extra).
50
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
