In this Leetcode Single Number problem solution, we have 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.

Leetcode Single Number problem solution


Problem solution in Python.

class Solution(object):
    def singleNumber(self, nums):
        map = {}
        if ( nums == [] ):
            return -1
        for d in nums:
            if ( d in map):
                del map[d]
            else:
                map[d] = 1
        return list(map.keys())[0]



Problem solution in Java.

class Solution {
    public int singleNumber(int[] nums) {
        
        int length = nums.length;
        if(length==1) return nums[0];
        Arrays.sort(nums);
        if(nums[1]!=nums[0]) {
            return nums[0];
        }
        if (nums[length-1]!=nums[length-2]){ 
            return nums[length-1];
        }
        for(int i=1; i<length-1; i++){
            if(nums[i]!=nums[i-1] && nums[i]!= nums[i+1]){
                return nums[i];
            }
        }
        return -1;
    }
}


Problem solution in C++.

class Solution
{
public:

int singleNumber(std::vector<int>& n) 
{
    if(n.size() == 1) return n[0];
    
    std::sort(n.begin(), n.end());
    
    if(n[0] != n[1]) return n[0];
    
    if(n[n.size() - 2 ] != n[n.size() - 1]) return n[n.size() - 1];
    
    for(size_t i = 0; i < n.size() - 2; i++)
    {
        if(n[i] != n[i+1] && n[i+1] != n[i+2])
        {
            return n[i+1];
        }
    }
    
    return 0;
}
};


Problem solution in C.

struct node {
     int key ;
     int val ;
     UT_hash_handle hh; 
};
int singleNumber (int A[], int n) {
    struct node *hashtable = NULL , *tmp = NULL, *ptr;
    for (int i =0 ; i< n ; i++){

        HASH_FIND_INT(hashtable, &A[i], tmp);
        if (tmp == NULL){
             ptr = (struct node *)malloc(sizeof(struct node));
             ptr->key =A[i] ;
             ptr->val =i;
             HASH_ADD_INT(hashtable,key,ptr);
        } else {
            A[tmp->val]=0; A[i]=0;
        }
    }
    for (int i=0 ; i < n ; i++){
        if (A[i]!=0)
        return A[i];
    }
}