# Sprint 2 Module Project 2
## Find the single number

"""
Understand

[1,1,2,1] --> 2

[2] --> 2

[1,1,2,2,3] --> 3

Plan
Use a dictionary to keep track of the number of times an element appears
Output the number that only appears once

Runtime: O(number of elements)
Space: O(number of elements)
"""

from collections import defaultdict

def csFindTheSingleNumber(nums):
    counts = defaultdict(int) # create a dictionary with a default value of 0
    for num in nums:
        counts[num] += 1

    for (key, value) in counts.items():
        if value == 1:
            return key

## Average of top five

"""
Understand

[[1, 5], [2, 1], [1, 3], [3, 0]]
student 1 avg score = 4
student 2 avg score = 1
student 3 avg score = 0

Plan
1. Use a dictionary to keep track of all the student's scores
  1.1 The dictionary key is the student id, the value will be a list of all their scores
2. Modify the dictionary values to get the average of the top 5 scores of the student
3. Append the student id and their average score in sorted order

Runtime: Upper-bounded by O(n * k log k) where n = the number of students and k = max number of scores of a student
Space: O(n) where n = the length of scores
"""

def csAverageOfTopFive(scores):
    studentScoreMapping = {}
    for (studentID, score) in scores:
        if studentID not in studentScoreMapping:
            studentScoreMapping[studentID] = []
        studentScoreMapping[studentID].append(score)

    for (studentID, scoresForStudent) in studentScoreMapping.items():
        scoresForStudent.sort(reverse=True)
        topFiveScores = scoresForStudent[:5]
        studentScoreMapping[studentID] = int(sum(topFiveScores) / len(topFiveScores))

    res = []
    studentIDs = sorted(studentScoreMapping.keys())
    for studentID in studentIDs:
        res.append([studentID, studentScoreMapping[studentID]])

    return res

## csMaxNumberOfLambdas

from collections import defaultdict

def csMaxNumberOfLambdas(text):
    charCount = defaultdict(int)
    for char in text:
        charCount[char] += 1
    hasLambda = True
    numLambda = 0
    while hasLambda:
        hasLambda = canConstructLambda(charCount)
        if hasLambda:
            numLambda += 1
    return numLambda
    
def canConstructLambda(charCount):
    for char in "lambda":
        if char not in charCount or charCount[char] == 0:
            return False
        charCount[char] -= 1
    return True