Problem Statement

Given an array nums sorted in non-decreasing order. Every number in the array except one appears twice. Find the single number in the array.

Examples

Example 1:

Input: nums = [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6]
Output: 4

Explanation: All other elements except 4 appears twice.

Example 2:

Input: nums = [1, 1, 3, 5, 5]
Output: 3

Explanation: All other elements except 3 appears twice.

Example 3:

Input: nums = [1, 1, 2, 2, 3, 3, 6, 6, 7]
Output: 7

Explanation: All other elements except 7 appears twice.

Constraints:

• n == nums.length
• 1 ≤ n ≤ 10^4
• -10^4 ≤ nums[i] ≤ 10^4

Different Approaches

1️⃣ Brute Force Approach 1

Intuition:

The idea here is to perform simple comparisons between elements in the array. During iteration, for each element, check if it is equal to either its previous or next element. If it is, then it is not the single element; otherwise, it is the single element.

Edge Case: If size of array equals 1, immediately return the only element in the array since it can't have a duplicate.

Handle the boundary cases (index 0 and index sizeOfArray - 1).

Code:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {1, 1, 2, 2, 3}; // Example with a unique element at the end
    
    for (int i = 0; i < arr.size(); i++) {
        int prev = (i == 0) ? -1 : arr[i - 1];       // Handle the first element case
        int next = (i == arr.size() - 1) ? -1 : arr[i + 1]; // Handle the last element case
        int curr = arr[i];
        
        if (curr != prev && curr != next) {
            cout << "Unique element: " << curr << endl;
            break;
        }
    }
}

Complexity Analysis:

• Time Complexity: O(N), where N is size of the array. As the array is being traversed only once using a single loop.
• Space Complexity: As no additional space is used, so the Space Complexity is O(1).

2️⃣ Brute Force 2

Intuition:

Here, the concept of XOR operation will be used to solve this problem. When XOR is applied to two identical numbers, it results in 0 (a XOR a = 0), and XOR of a number with 0 gives the number itself (a XOR 0 = a). Therefore, iterate through the array and perform XOR on each element. Numbers that appear twice will cancel out to zero, leaving only the single number as the answer.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the single non
    duplicate element in a sorted array */
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size(); // Size of the array.
        int ans = 0;
        
        /* XOR all the elements to find 
        the single non-duplicate element.*/
        for (int i = 0; i < n; i++) {
            ans = ans ^ nums[i];
        }
        
        /* Return the single non 
        duplicate element found.*/
        return ans;
    }
};

int main() {
    vector<int> nums = {1, 1, 2, 2, 3, 3, 4};
    
    // Create an object of the Solution class.
    Solution sol;
    
    int ans = sol.singleNonDuplicate(nums);
    
    // Print the result.
    cout << "The single element is: " << ans << "\n";
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N), where N is size of the array. As the array is being traversed only once using a loop.
• Space Complexity: As no additional space is used, so the Space Complexity is O(1).

3️⃣ Optimal Approach

Intuition:

In a sorted array where each element appears exactly twice except for one unique element, the pairs of identical elements (e.g., [1,1,2,2,3,3,...]) will always be positioned in such a way that:

1. The first occurrence of each element is at an even index.
2. The second occurrence of each element is at an odd index.

However, as soon as the unique element appears, this pattern breaks. For example:

• Before the unique element, all pairs have the first instance on even indices and the second instance on odd indices.
• After the unique element, this pairing shifts—pairs start with the first occurrence at odd indices and the second occurrence at even indices.

Using this property, we can identify the unique element by finding where the pattern breaks.

Approach:

1. Binary Search: Use binary search to find the unique element. Initialize low as 0 and high as the last index of the array.
2. Check Middle Element: Calculate the middle index mid as (low + high) / 2. There are two main cases:
   • If mid is even, check if arr[mid] is equal to arr[mid + 1]. If they’re equal, it means the unique element lies on the right side; otherwise, it’s on the left.
   • If mid is odd, check if arr[mid] is equal to arr[mid - 1]. If they’re equal, it means the unique element lies on the right side; otherwise, it’s on the left.
3. Adjust Search Range:
   • If the pair pattern is correct on the left side of mid, move low to mid + 1.
   • If the pair pattern is broken on the left, move high to mid.
4. Termination: When low equals high, low will be pointing at the unique element.

Dry Run:

Code:

#include <vector>
using namespace std;

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        
        // Initialize the search bounds
        int left = 0, right = n - 1, mid;

        // Perform binary search to find the unique element
        while (left <= right) {
            mid = left + (right - left) / 2;

            // Check if `mid` is at the boundaries or is the unique element
            if (mid == 0 || mid == n - 1 || (nums[mid] != nums[mid + 1] && nums[mid] != nums[mid - 1])) {
                break;
            }

            // Determine the direction to continue the search
            if (mid % 2 == 0) {
                // For even `mid`, check if the pair is on the right side
                if (nums[mid] == nums[mid + 1]) {
                    left = mid + 1; // Move to the right half
                } else {
                    right = mid - 1; // Move to the left half
                }
            } else {
                // For odd `mid`, check if the pair is on the left side
                if (nums[mid] == nums[mid - 1]) {
                    left = mid + 1; // Move to the right half
                } else {
                    right = mid - 1; // Move to the left half
                }
            }
        }

        // `mid` will be pointing to the unique element
        return nums[mid];
    }
};

OR

Observe Patterns:
1] 1 1 2 3 3 4 4
mid = 7/2 = 3, and we see that nums[3] and nums[4] is same, 
so target is on left.

2] 1 1 3 3 4 5 5
mid = 7/2 = 3, and we see that nums[3] and nums[4] is not same, 
so target is on right.

3] 1 1 2 3 3 4 4 5 5
mid = 9/2 = 4, do mid = mid + 1 = 5, and nums[5] and nums[6] is same, 
so target is on left.

4] 1 1 2 2 3 3 4 5 5
mid = 9/2 = 4, do mid = mid + 1 = 5, and nums[5] and nums[6] is not same, 
so target is on right.

for this to work we have to always keep mid as odd index
except when mid is 0 and i == j

#include <vector>
using namespace std;

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // Ensure `mid` is even for consistent pair checking (if odd, decrement by 1)
            if (mid % 2 == 1) mid--;

            // Check if the pair is valid
            if (nums[mid] == nums[mid + 1]) {
                // Pair is on the right, move left bound up
                left = mid + 2;
            } else {
                // Pair is broken, move right bound down
                right = mid;
            }
        }

        // `left` will be pointing to the unique element
        return nums[left];
    }
};

Complexity:

• Time complexity: O(logn)
• Space complexity: O(1)