Practice/Amazon/Leetcode 136. Single Number

Leetcode 136. Single Number

CodingOptional

Problem

You are given a non-empty array of integers where every integer appears exactly twice, except for one integer that appears only once. Your task is to identify and return that single unique integer.

Your solution must run in linear time complexity O(n) and use constant space complexity O(1).

Requirements

1. Return the integer that appears exactly once in the array
2. Achieve O(n) time complexity
3. Achieve O(1) space complexity (no additional data structures proportional to input size)
4. Handle both positive and negative integers
5. Handle the case where the array contains only one element

Constraints

• 1 ≤ nums.length ≤ 30,000
• -30,000 ≤ nums[i] ≤ 30,000
• Every integer appears exactly twice except for one integer that appears once

Examples

Example 1:

Input: nums = [4, 1, 2, 1, 2] Output: 4 Explanation: The numbers 1 and 2 each appear twice, while 4 appears only once.

Example 2:

Input: nums = [2, 2, 1] Output: 1 Explanation: The number 2 appears twice, and 1 appears once.

Example 3:

Input: nums = [7] Output: 7 Explanation: There is only one element in the array, so it must be the unique one.

Example 4:

Input: nums = [-5, 3, -5, 3, 7, 8, 8] Output: 7 Explanation: All numbers appear in pairs except for 7.