Problem Statement

Given an array of integers, with the exception of one number that appears exactly once while all other appear more than once. The task is to identify this lone number amidst its more common counterparts.

Examples:

Example 1:

Input: arr[] = {2, 2, 1, 4, 1, 5, 5}

Output: 4

Different Approaches

1 Brute Force Method

The simplest approach involves iterating through the array and comparing each element with all other elements to count its occurrences. Once a number with only one occurrence is found, its's marked as the lone number.

Algorithm

1. We will traverse the array using a loop to select each element one by one.
2. For each selected element, we will perform a linear search using another loop to count its occurrence within the array.
3. If the count of occurrences for any element is 1, we will identify it as the lone number and return it.

Code

#include <iostream>
#include <vector>

using namespace std;

int findLoneNumber(const vector<int>& arr) {
    // Iterate through each element of the array
    for (int i = 0; i < arr.size(); ++i) {
        int count = 0; // Initialize count for current element
        // Linear search to count occurrences of arr[i]
        for (int j = 0; j < arr.size(); ++j) {
            if (arr[i] == arr[j]) {
                count++;
            }
        }
        // If count is 1, return the lone number
        if (count == 1) {
            return arr[i];
        }
    }
    // Return -1 if no lone number is found
    return -1;
}

int main() {
    vector<int> arr = {2, 2, 1, 4, 1, 5, 5};
    int loneNumber = findLoneNumber(arr);
    if (loneNumber != -1) {
        cout << "The lone number is: " << loneNumber << endl;
    } else {
        cout << "No lone number found in the array." << endl;
    }
    return 0;
}

Complexity Analysis

Time Complexity:

• Since there are two loops that runs n times, so the time complexity is O(n^2), where n is the number of elements in the array.

Space Complexity:

• O(1) as we are not using any extra space.

2 Hash Map Approach

By utilizing a hash map to store the count of occurrences of each number in the array, we can efficiently identify the lone number by examining the counts. After populating the hash map, we iterate through it to find the number with only one occurrence.

Algorithm

1. First, we declare a map.
2. Now, using a loop we will store the elements of the array along with their frequency in the map data structure.
3. Using another loop we will iterate over the map, and try to find the element for which the frequency is 1, and finally, we will return that particular element.

Code:

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

int getSingleElement(vector<int> &arr) {

    //size of the array:
    int n = arr.size();

    // Declare the hashmap.
    // And hash the given array:
    map<int, int> mpp;
    for (int i = 0; i < n; i++) {
        mpp[arr[i]]++;
    }

    //Find the single element and return the answer:
    for (auto it : mpp) {
        if (it.second == 1)
            return it.first;
    }

    //This line will never execute
    //if the array contains a single element.
    return -1;
}

int main()
{
    vector<int> arr = {4, 1, 2, 1, 2};
    int ans = getSingleElement(arr);
    cout << "The single element is: " << ans << endl;
    return 0;
}

Complexity Analysis

Time Complexity:O(N * logM) + O(M), where M = size of the map i.e., M = (N/2) +1. N = size of the array.

• We are inserting N elements in the map data structure and insertion takes logM time (where M = size of the map). So this results in the first term O(N * logM). The second term is to iterate the map and search the single element.

Space Complexity: O(M) as we are using a map data structure.

3 Bit Manipulation (XOR)

We can efficiently identify the lone number, XORing a number with itself results in zero, so XORing all elements of the array will cancel out the numbers that appear multiple times, leaving us with lone number.

Two Properties of XOR (exclusive OR)

XOR of Two same numbers is always 0

– 1 XOR 1 = 0

– 0 XOR 0 = 0

XOR of a Number with 0 is the Number itself.

– 0 XOR 1 = 1

Hence all the numbers except the single number appear twice and so will form a pair. Now, if we perform XOR of all element of the array, the XOR of each pair will result in 0 according to the XOR property 1. The result will be = 0 ^ (single number) = single number (according to property 2)

Code:

#include <iostream>
#include <vector>

using namespace std;

int findLoneNumber(const vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

int main() {
    vector<int> nums = {2, 2, 1, 4, 1, 5, 5};
    int loneNumber = findLoneNumber(nums);
    cout << "The lone number is: " << loneNumber << endl;
    return 0;
}

Complexity Analysis

Time Complexity:O(N)

Space Complexity: O(1)