Leetcode 540: Single Element in a Sorted Array

Input: The input is a sorted array of integers where every element appears exactly twice, except for one element.

Example: Input: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]

Constraints:

• 1 <= nums.length <= 10^5

• 0 <= nums[i] <= 10^5

Output: Return the single element that appears only once in the array.

Example: Output: 2

Constraints:

• The returned element will be the one that appears only once.

Goal: Find the single element that appears only once in the sorted array.

Steps:

• Initialize a result variable to 0.

• Iterate through the array and XOR each element with the result.

• After completing the loop, the result will contain the single element that appears only once.

Goal: The array is sorted and contains only integers where every element appears exactly twice, except for one element.

Steps:

• The input list contains between 1 and 10^5 integers.

• Each integer in the array is between 0 and 10^5.

Assumptions:

• The array will always contain at least one element.

• The array is sorted.

• Input: Input: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]

• Explanation: The only element that doesn't have a pair is 2, so the output is 2.

Approach: To solve this problem, we use the XOR operation which helps to cancel out duplicate elements. Since every element except one appears exactly twice, XORing all elements will result in the unique element.

Observations:

• The XOR operation can be used to identify the unique element because it cancels out identical numbers.

• Since the array is sorted, and we only need to find one unique element, XOR provides a time-efficient way to solve this problem in O(n) time with constant space.

Steps:

• Initialize a variable `result` to 0.

• Loop through the array, XOR each element with `result`.

• At the end of the loop, `result` will contain the unique element that appears only once.

Empty Inputs:

• The array will not be empty, as the problem guarantees at least one element.

Large Inputs:

• Ensure the solution handles up to 10^5 elements efficiently.

Special Values:

• Handle arrays with the smallest and largest values, ensuring the XOR operation works for all integers within the given range.

Constraints:

• The input list contains valid integers within the specified range.

int singleNonDuplicate(vector<int>& nums) {
    int res = 0;
    for(int num : nums)
    res ^= num;

    return res;
}

1 : Function Definition

int singleNonDuplicate(vector<int>& nums) {

Defines the function `singleNonDuplicate`, which takes a vector of integers `nums` as input and returns the single non-duplicate element using the XOR bit manipulation technique.

2 : Variable Initialization

    int res = 0;

Initializes a variable `res` to 0, which will store the result of the XOR operations. This will eventually hold the single non-duplicate element.

3 : Loop

    for(int num : nums)

Begins a loop that iterates over each element in the `nums` vector.

4 : XOR Operation

    res ^= num;

Applies the XOR operation between `res` and the current element `num`. The XOR operation helps to cancel out duplicate elements, leaving only the non-duplicate element.

5 : Empty Line

Represents an empty line in the code, separating different sections.

6 : Return Statement

    return res;

Returns the result stored in `res`, which is the single non-duplicate element in the array.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the number of elements in the array.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1), as we only need a constant amount of extra space for the result.

Leetcode 540: Single Element in a Sorted Array

Solution to LeetCode 540: Single Element in a Sorted Array Problem

Explore →