LeetCode //C - 136. Single Number

136. Single Number

Given a non-empty array of integers nums, 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

Constraints:

• $1<=nums.length<=3\ast 10^4$
• $-3\ast 10^4<=nums[i]<=3\ast 10^4$
• Each element in the array appears twice except for one element which appears only once.

From: LeetCode
Link: 136. Single Number

---

Solution:

Ideas：

• We initialize result to 0.
• We iterate through the nums array using a for loop.
• For each element in nums, we perform an XOR operation with result.
• Since XOR of a number with itself is 0, and XOR of a number with 0 is the number itself, all elements appearing twice will cancel out.
• The remaining number, which appears only once, will be the final value of result.
• Finally, we return result, which is the single number in the array.

Code:

int singleNumber(int* nums, int numsSize) {
    int result = 0;
    for (int i = 0; i < numsSize; i++) {
        result ^= nums[i];
    }
    return result;
}

1
2
3
4
5
6
7
8