136. Single Number

Description

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [2, 2, 1]

Output: 1

Example 2

Input: [4, 1, 2, 1, 2]

Output: 4

Solutions

Solution 1

/**
 * Time complexity : O(n*1) = O(n). Time complexity of for loop is O(n). 
 *    Time complexity of hash table(dictionary in python) operation pop is O(1).
 * Space complexity : O(n). The space required by hash_table is equal to the 
 *    number of elements in nums.
 */

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1) return nums[0];
        
        int value = 0;
        if(nums.length%2 == 0) return value;
        
        Map<Integer, Integer> values = new HashMap();
        for(int n: nums) {
            values.put(n, values.getOrDefault(n, 0)+1);
        }
        
        for(int n: nums) {
            if(values.get(n) == 1) {
                return n;
            }
        }
        
        return value;
    }
}

Solution 2

/**
 * Time complexity : O(n+n)=O(n). sum will call next to iterate through nums. 
 *    We can see it as sum(list(i, for i in nums)) which means the time 
 *    complexity is O(n) because of the number of elements(n) in nums.
 * Space complexity : O(n+n)=O(n). set needs space for the elements in nums
 */
 
 class Solution {
  public int singleNumber(int[] nums) {
    int sumOfSet = 0, sumOfNums = 0;
    Set<Integer> set = new HashSet();

    for (int num : nums) {
      if (!set.contains(num)) {
        set.add(num);
        sumOfSet += num;
      }
      sumOfNums += num;
    }
    return 2 * sumOfSet - sumOfNums;
  }
}

Solution 3

/**
 * Time complexity : O(n). We only iterate through nums, so the time 
 *    complexity is the number of elements in nums.
 * Space complexity : O(1)
 */
 
 class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1) return nums[0];
        
        int value = 0;
        if(nums.length%2 == 0) return value;

        for(int n: nums) {
            value ^= n;
        }
        
        return value;
    }
}

Follow up