Single Number

https://leetcode.com/problems/single-number§/

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Solution:

Oh, that task was super popular a few years ago. Especially Luxoft and other body shops asked it.

Before we start. Do you like bit operations? Oh, I`m not a big fan of it. You just have to learn the base rules.

Do you know XOR operation? '^' do you know how it works? This operation calls "exclusive or". If you have two digits like 1 and 1 and do 1 ^ 1 it will be 0. If you do 1^1 it will be 1.

That is mean if we do smth 10101 ^ 10101 we will get 0. Is it clear?

And now we can solve our problem.

We know that in the array we have duplicates for all numbers except one. So, iterating over the array and using the XOR operation will solve the problem.

  public int singleNumber(int[] nums) {
    int rez = 0;
     
    for(int i = 0; i < nums.length; i++){
      rez ^= nums[i];
    }
    return rez;
  }