Single Number

Problem Statement

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

Examples

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

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

Input: nums = [1] Output: 1

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Time Complexity should be O(n) and Space Complexity should be O(1).

Approach

As given in the question, that all the elements will appear twice in the array except one. Here we can use XOR of the elements as A^A=0 while traversing the array would result in the answer.

Code

public int singleNumber(int[] nums) {
    int num =0;
    for(int i: nums)
    num ^= i;
    
    return num;
    }

Complexities

Time Complexity: O(n) as visiting all the elements only once.

Space Complexity: O(1) as only taking a variable to store xor of all the elements in the array.