Find a single number that doesn't appear twice 1️⃣

Theory to get started

In this problem we take a best approach to just use hashmap and check for the frequency of counts stored inside the hashmap.

We can even implement this in more optimal way by making use of XOR instead of hashmap, but that is not covered in this document

Here is the breakdown of the steps in the code:

/* 
    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.

    here linear runtime complexity means:
    Your algorithm must run in O(n) time, where n is the size of the input.
*/
#include<stdio.h>
#include<vector>
#include<iostream>
#include <map>

using namespace std;

int singleNumber(vector<int>& nums){
    int size = nums.size();
    /* step1: declare hashmap */
    /* map key is number and value is frequence ie. also number */
    map<int, int> customMap;
    /* step2: increment the frequency, here hashmap stores unique keys */
    for(int i=0; i<size; i++){
        customMap[nums[i]]++; 
    }
    /* step3: iterate throught the hashmap and check if any value is equal to 1 */
    for (const auto& pair : customMap) {
        if(pair.second == 1){
            /* if value is found to be one, then return the corresponding key */
            return pair.first;
        }
    }
    return -1;
}

int main(){
    int n;
    cin >> n;

    vector<int> arr(n);
    for(int i=0; i<arr.size(); i++){
        cin >> arr[i];
    }

    int ans = singleNumber(arr);
    cout << ans;
    return 0;
}

[Top]