# CSPT23 Lecture 3
## [Single Number](https://leetcode.com/problems/single-number/)

class Solution:
    """
    Understand
    
    nums = [2,2,1]
    output = 1
    
    nums = [1]
    output = 1
    
    nums = [4,1,2,1,2]
    output = 4
    
    Plan
    Brute-force
    For each number, check if that number occurs only once
    
    Use a dictionary to keep track of the counts per each element (key = element, value = num times element occurs)
    """
    def singleNumber(self, nums: List[int]) -> int:
        counts = {}
        for num in nums:
            if num not in counts:
                counts[num] = 1
            else:
                counts[num] += 1
        for (num, numOccurences) in counts.items():
            if numOccurences == 1:
                return num

## [Two Sum](https://leetcode.com/problems/two-sum/)

class Solution:
    """
    Plan
    Brute-force
    Generate all pairs until we find the correct one
    
    Optimized
    initialize a dictionary that stores the complement number as the key and the value its index
    iterate for each element and if a complement is found, then output the correct indices
    """
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i, num in enumerate(nums):
            if target - num in d:
                return [d[target - num], i]
            d[num] = i
    
    def bruteForcetwoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]