# Trace 1:
# 12 bc a
# bc  da
# bc  d

# Trace 2:
# 5 9 13 (22, 5)
# 7 11 (17, 7)

# Trace 3:
# rock you we will


# Trace 4:
# 2 e c 3 d 
# 0 _ _ 1 _ 

# Trace 5:
# b[i%x]:  5 

# b[i%x]:  6 

# [[2, 5], [6, 8]]

def nthHarshadNumber(n):
    count = 0
    guess = 9 # the first one is 10!
    while (count != n):
        guess += 1
        if (isHarshadNumber(guess)):
            count += 1
    return guess

def isHarshadNumber(guess):
    # get sum of digits in guess
    Sum = 0
    temp = guess
    while (temp != 0):
        # get a digit
        digit = temp % 10
        # add it to sum
        Sum += digit
        # shift digits right by 1
        temp /= 10
    # see if number divisible by sum
    if ((guess % Sum) == 0):
        return True
    else:
        return False

def getTimeString(totalMinutes):
    # get the number of hours passed
    hours = totalMinutes / 60 # integer division!
    # get the number of minutes
    totalMinutes %= 60 # get the remainder!
    # now get total hours passed since midnight
    while (hours > 12):
        hours -= 12 # deal with wrap around
    # check for hours = 0 edge case!
    if hours == 0: hours = 12
    # check to see if minutes is a single digit
    if (len(str(hours)) != 2): 
        hours = "0" + str(hours)
    if (len(str(totalMinutes)) != 2):
        totalMinutes = "0" + str(totalMinutes)
    # build final answer
    answer = str(hours) + ":" + str(totalMinutes)
    return answer

def duplicates(a):
    # get a copy of list since we cannot modify it
    b = range(0, len(a))
    for index in range(0, len(a)):
        temp = a[index]
        b[index] = temp
    # now check for duplicates
    dup = list()
    for x in b:
        # see if element x is a duplicate
        if (b.count(x) > 1):
            temp = x
            # if that duplicate isn't accounted for, add it
            if temp not in dup:
                dup += [temp]
    # now sort the list of dulpicates
    dup.sort() # not sorted()!
    return dup

def reverseString(s):
    # set up reverse string
    rev = ""
    # loop backwards through string
    for i in range(-1, -(len(s) + 1), -1):
        temp = s[i]
        rev += temp
    return rev

def vowelCount(s):
    count = 0 # vowel count
    # make vowels list
    vowels = ["a", "e", "i", "o", "u"]
    # loop through string
    for c in s.lower():
        # see if the char is a vowel
        if c in vowels:
            count += 1
    return count

def rangeSum(lo, hi):
    # base case
    if (lo > hi): return 0
    # recursive case
    else: return (lo + rangeSum(lo+1, hi))

def interleave(list1, list2):
    # edge case:
    if (len(list1) != len(list2)):
        raise Exception("Lists are not the same length!")
    # base case:
    elif (len(list1) == 0): return []
    # recursive case:
    else: return [list1[0] , list2[0]] + interleave(list1[1:], list2[1:])

def selectionsort(L):
    if (len(L) < 2):
        return L
    else:
        i = L.index(min(L))
        return [L[i]] + selectionsort(L[:i] + L[i+1:])