interviewPlayground.swift

// Time O(n), Space O(1)
func hasConsecutiveOdds(_ nums: [Int]) -> Bool {
    var oddCount = 0
    var index = 0
    
    while index != nums.count
    {
        if nums[index] % 2 == 1 {
            oddCount += 1
            if oddCount == 3 { return true }
        } else {
            oddCount = 0
        }
        
        index += 1
    }
    
    return false
}


//----------------------------------------------------------//
// Time O(n), Space O(n)
func reverseVowels(_ str: String) -> String {
    let strCount = str.count
    if (strCount < 2) { return str }
    
    var left = 0
    var right = strCount - 1
    var foundLeft = false
    var foundRight = false
    
    var strArr = Array(str)
    while left < right {
        if !foundLeft {
            if isVowel(strArr[left]) { foundLeft = true } else { left += 1 }
        }
        if !foundRight {
            if isVowel(strArr[right]) { foundRight = true } else { right -= 1 }
        }
        
        if foundLeft == true && foundRight == true {
            strArr.swapAt(left, right)
            left += 1
            right -= 1
            foundLeft = false
            foundRight = false
        }
    }
    
    return String(strArr)
}

func isVowel(_ char: Character) -> Bool {
    return "iaeou".contains(char) ? true : false
}



//----------------------------------------------------------//
// Time O(nlogn) Space O(n)
func divideCandies(_ candies: [Int]) {
    let sortedCandies = candies.sorted()
    let count = sortedCandies.count
    // each kid takes half of the bucket, at first
    var a = Array(sortedCandies[0..<count/2])
    var b = Array(sortedCandies[count/2..<count])
    
    // number of candies each kid owns
    var aSum = a.reduce(0, +)
    var bSum = b.reduce(0, +)
    var dif = bSum - aSum
    
    let min = sortedCandies[0]
    while dif > min {
        if bSum > aSum {
            let takingIndex = indexOfCandy(closestTo: dif / 2, in: b)
            let taken = b.remove(at: takingIndex)
            let givingIndex = search(for: taken, in: a)
            
            if a[givingIndex] < taken {
                a.append(taken)
            } else {
                a.insert(taken, at: givingIndex)
            }
            
            aSum += taken
            bSum -= taken
        } else {
            let takingIndex = indexOfCandy(closestTo: dif / 2, in: a)
            let taken = a.remove(at: takingIndex)
            let givingIndex = search(for: taken, in: b)
            
            if b[givingIndex] < taken {
                b.append(taken)
            } else {
                b.insert(taken, at: givingIndex)
            }
            
            aSum -= taken
            bSum += taken
        }
        
        dif = abs(bSum - aSum)
    }
    
    print(a)
    print(b)
}


func indexOfCandy(closestTo val: Int, in nums: [Int]) -> Int {
    let i = search(for: val, in: nums)
    if nums[i] == val || i == 0 { return i }
    return  nums[i] - val > val - nums[i - 1] ? i - 1 : i
}

func search(for val: Int, in nums: [Int]) -> Int {
    var left = 0
    var right = nums.count - 1
    
    while left + 1 < right {
        let mid = (right / 2) + left
        if (nums[mid] < val) {
            left = mid
        } else if (nums[mid] > val) {
            right = mid
        } else {
            return mid
        }
    }
    if (nums[left] >= val) { return left }
    return right
}