May Leetcode Speedrun Question: Single element in a Sorted Array

Question

So I was watching Errichto complete these challenges and I was amazed at how fast he solved the "Single element in a Sorted Array". From a beginner's perspective, it does look impressive - maybe for senior devs the speed is quite normal.

You are given a sorted array where all elements are integers, and all elements appear exactly twice in the array, except for one element, which appears exactly once. (i.e., all elements are duplicated, except one.) You need to find the element appearing exactly once.

I am just here to understand how said code works:

class Solution { 
public:
    int singleNonDuplicate(vector<int>& nums) {
        long long a = 0;
        for(int x : nums) {
            a ^= x
        }
        return a;
    }
};

Here's what I've got so far: for every single integer "x" in the vector/array "nums", a is equal to a^x (if what I said is correct).

And here are my questions:

Wouldn't a^x be equal to 0 because a is 0 since the beginning?

int singleNonDuplicate(vector<int> nums) {
//...
}

and

int singleNonDuplicate(vector<int>& nums) {
//...
}

I've understood this: vector<int> nums is pass by value (you're working with a "copy" of nums inside the function) and vector<int>& nums is pass by reference (you're working with nums itself inside the function).

Does the "&" matter if you were to solve the problem just like Errichto?

ps:

sorry for possible mistakes from a programming perspective, I might've accidentally said some wrong things.
yes I will learn C++ sooner or later, 2020 is the first year in my life where I actually have an actual "programming" class in my schedule, these videos are entertaining and I'm curious to see why said code works & try understand etc.

I don't know what leetcode is, or the speedrun question you're referring to. Please make the question self-contained, by adding the actual problem as well. — cigien, Oct 17 '20 at 17:09
This is a very common beginner problem. It's been asked and answered many times on SO, here's [one of the multiple duplicates](https://stackoverflow.com/questions/35185/finding-a-single-number-in-a-list). Note that this solution is linear time O(n) and slower than it could be. Since the array is sorted it can be done in O(log n) time. — Blastfurnace, Oct 17 '20 at 17:22
@cigien "You are given an unsorted array where all elements are integers, and all elements appear exactly twice in the array, except for one element, which appears exactly once. (i.e., all elements are duplicated, except one.)" this is the text for the problem & my bad for not implementing it into my original post, will do that for further questions — cezar, Oct 17 '20 at 17:28
Is the array sorted or unsorted? Your question says both and the [leetcode question](https://leetcode.com/problems/single-element-in-a-sorted-array/) I found says it's sorted. — Blastfurnace, Oct 17 '20 at 17:32
@Blastfurnace sorted, sorry for not specifying. I've looked into a couple youtube videos and I've started to understand how this type of beginner exercise works :) Thanks for willing to help! — cezar, Oct 17 '20 at 17:41
@cezar Beginners don't do exercises like this. This is almost trivia -- beginners should spend their time actually learning the language first, not focus on trivia like this. — PaulMcKenzie, Oct 17 '20 at 17:59
Aside: `long long a = 0;` is strange given `vector nums`. I'd expect `int a = 0;` or perhaps `unsigned a = 0;`. — chux - Reinstate Monica, Oct 18 '20 at 14:42

ajm · Answer 1 · 2020-10-17T17:23:59.377

Casual proof:

(If you're interested in areas of study that help you to come up with solutions like this and understand them, I'd suggest Discrete Mathematics and Group Theory / Abstract Algebra.)

I think I know the question you were referencing. It goes something like,

You are given an unsorted array where all elements are integers, and all elements appear exactly twice in the array, except for one element, which appears exactly once. (i.e., all elements are duplicated, except one.)

You're on the right track for the first part, why the algorithm works. It takes advantage of a few properties of XOR:

X^0=X
X^X=0
The XOR operation is commutative and associative.

# proof

# since XOR is commutative, we can take advantage
# of the fact that all elements except our target
# occur in pairs of two:

P1, P1 = Two integers of the same value in a pair.
T = Our target.

# sample unsorted order, array size = 7 = (3*2)+1
[ P3, P1, T, P1, P2, P3, P2 ]

# since XOR is commutative, we can re-arrange the array
# to our liking, and still get the same value as
# the XOR algorithm.

# here, we move our target to the front, and then group
# each pair together.  I've arranged them in ascending
# order, but that's not important:

[ T, P1, P1, P2, P2, P3, P3 ]

# write out the equation our algorithm is solving:
solution = 0 ^ T ^ P1 ^ P1 ^ P2 ^ P2 ^ P3 ^ P3

# because XOR is associative, we can use parens
# to indicate elements of the form X^X=0:
solution = T ^ (P1 ^ P1) ^ (P2 ^ P2) ^ (P3 ^ P3) ^ 0

# substitute X^X=0
solution = T ^ 0 ^ 0 ^ 0 ^ 0

# use X^0=X repeatedly
solution = T

So we know that running that algorithm will give us our target, T.

On using `&` to pass-by-reference instead of pass-by-value:

Your understanding is correct. Here, it doesn't make a real difference.

Pass-by-reference lets you modify the original value in place, which he doesn't do.

Pass-by-value copies the vector, which wouldn't meaningfully impact performance here.

So he gets style points for using pass-by-reference, and if you're using leetcode to demonstrate your diligence as a software developer it's good to see, but it's not pertinent to his solution.

great & in depth explanation, will try my best to understand it — cezar, Oct 17 '20 at 17:25

score 0 · Answer 2 · answered Oct 17 '20 at 17:19

^ is XOR operation in the world of coding, not the power operation (which you are assuming I guess).

I don't know about which problem you are talking about, if its finding the only unique element in array (given every other element occurs twice),

then the logic behind solving is

             **a XOR a equals 0 **

             **a XOR 0 equals a**

So if we XOR all the elements present in array, we will get 0 corresponding to the elements occurring twice. The only element remaining will be XORed with 0 and hence we get the element.

Answer to second query is that whenever you want to modify the array we pass it by reference .

PS: I am also new to programming.I hope I answered your queries.

yea it makes sense and you have answered my question, will read about XOR soon to understand what the whole deal is (your answer is quite simple & easy to understand for people like me, so thank you for that ! ) — cezar, Oct 17 '20 at 17:26

May Leetcode Speedrun Question: Single element in a Sorted Array

2 Answers2

Casual proof:

On using & to pass-by-reference instead of pass-by-value:

On using `&` to pass-by-reference instead of pass-by-value: