Magical Candy BagsYou have N bags of candy. The ith bag contains arr[i] pieces of candy, and each of the bags is magical!It takes you 1 minute to eat all of the pieces of candy in a bag (irrespective of how many pieces of candy are inside), and as soon as you finish, the bag mysteriously refills. If there were x pieces of candy in the bag at the beginning of the minute, then after you’ve finished you’ll find that floor(x/2) pieces are now inside.You have k minutes to eat as much candy as possible. How many pieces of candy can you eat?

Signature

int maxCandies(int[] arr, int K)

Input

1 ≤ N ≤ 10,000 1 ≤ k ≤ 10,000 1 ≤ arr[i] ≤ 1,000,000,000

Output

A single integer, the maximum number of candies you can eat in k minutes.

Example 1

N = 5 k = 3 arr = [2, 1, 7, 4, 2] output = 14In the first minute you can eat 7 pieces of candy. That bag will refill with floor(7/2) = 3 pieces.In the second minute you can eat 4 pieces of candy from another bag. That bag will refill with floor(4/2) = 2 pieces.In the third minute you can eat the 3 pieces of candy that have appeared in the first bag that you ate.In total you can eat 7 + 4 + 3 = 14 pieces of candy.

func maxCandies(arr: [Int], k: inout Int) -> Int {
	var heap = Heap<Int>(elements: [2, 1, 7, 4, 2], priorityFunction: >)
	var maxSum = 0
	while k > 0 {
		guard var highest = heap.dequeue() else {
			return maxSum
		}
		maxSum += highest
		let nextFloor = Int(floor(Double(highest)/2.0))
		heap.enqueue(nextFloor)
		k -= 1
	}
	return maxSum;
}
var k = 3
print(maxCandies(arr: [2, 1, 7, 4, 2], k: &k))

struct Heap<Element>
{
	var elements : [Element]
	let priorityFunction : (Element, Element) -> Bool

	init(elements: [Element] = [], priorityFunction: @escaping (Element, Element) -> Bool) {
		self.elements = elements
		self.priorityFunction = priorityFunction
		buildHeap()
	}

	mutating func buildHeap() {
		for index in (0 ..< count / 2).reversed() {
			siftDown(elementAtIndex: index)
		}
	}
	
	var isEmpty : Bool { return elements.isEmpty }
	var count : Int { return elements.count }

	func peek() -> Element? {
		return elements.first
	}

	mutating func enqueue(_ element: Element) {
		elements.append(element)
		siftUp(elementAtIndex: count - 1)
	}

	mutating func siftUp(elementAtIndex index: Int) {
		let parent = parentIndex(of: index)
		guard !isRoot(index),
			isHigherPriority(at: index, than: parent)
			else { return }
		swapElement(at: index, with: parent)
		siftUp(elementAtIndex: parent)
	}

	mutating func dequeue() -> Element? {
		guard !isEmpty
			else { return nil }
		swapElement(at: 0, with: count - 1)
		let element = elements.removeLast()
		if !isEmpty {
			siftDown(elementAtIndex: 0)
		}
		return element
	}
	
	mutating func siftDown(elementAtIndex index: Int) {
		let childIndex = highestPriorityIndex(for: index)
		if index == childIndex {
			return
		}
		swapElement(at: index, with: childIndex)
		siftDown(elementAtIndex: childIndex)
	}

	// Helper functions
	
	func isRoot(_ index: Int) -> Bool {
		return index == 0
	}
	
	func leftChildIndex(of index: Int) -> Int {
		return (2 * index) + 1
	}
	
	func rightChildIndex(of index: Int) -> Int {
		return (2 * index) + 2
	}
	
	func parentIndex(of index: Int) -> Int {
		return (index - 1) / 2
	}
	
	func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool {
		return priorityFunction(elements[firstIndex], elements[secondIndex])
	}
	
	func highestPriorityIndex(of parentIndex: Int, and childIndex: Int) -> Int {
		guard childIndex < count && isHigherPriority(at: childIndex, than: parentIndex)
			else { return parentIndex }
		return childIndex
	}
	
	func highestPriorityIndex(for parent: Int) -> Int {
		return highestPriorityIndex(of: highestPriorityIndex(of: parent, and: leftChildIndex(of: parent)), and: rightChildIndex(of: parent))
	}
	
	mutating func swapElement(at firstIndex: Int, with secondIndex: Int) {
		guard firstIndex != secondIndex
			else { return }
		elements.swapAt(firstIndex, secondIndex)
	}
}

// A bonus extra for you: two extra functions, if the Element type is Equatable
extension Heap where Element : Equatable {
	
	// This function allows you to remove an element from the heap, in a similar way to how you would dequeue the root element.
	mutating func remove(_ element: Element) {
		guard let index = elements.index(of: element)
			else { return }
		swapElement(at: index, with: count - 1)
		elements.remove(at: count - 1)
		siftDown(elementAtIndex: index)
	}

	// This function allows you to 'boost' an element, by sifting the element up the heap. You might do this if the element is already in the heap, but its priority has increased since it was enqueued.
	mutating func boost(_ element: Element) {
		guard let index = elements.index(of: element)
			else { return }
		siftUp(elementAtIndex: index)
	}
}

var heap = Heap<Int>(elements: [3, 2, 8, 5, 0], priorityFunction: >)
heap.enqueue(6)
heap.enqueue(1)
heap.enqueue(4)
heap.enqueue(7)