Question: https://codility.com/demo/take-sample-test/rectangle_builder_greater_area/

Question Name: Rectangle-Builder-Greater-Area or RectangleBuilderGreaterArea

This key is the binary search.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
def solution(A, X): fence_count = {} for fence in A: fence_count[fence] = fence_count.get(fence, 0) + 1 num_of_pens = 0 usable_fences = [] for fence in fence_count: if fence_count[fence] < 2: # Less than one pair. We cannot use it. continue elif fence_count[fence] < 4: usable_fences.append(fence) else: usable_fences.append(fence) # We consider the square pen here. if fence * fence >= X: num_of_pens += 1 # We consider the non-square pen here. usable_fences.sort() candidate_size = len(usable_fences) for i in xrange(candidate_size): # Use binary search to find the first fence pair, that # could be used with current pair to form a pen. begin = i + 1 end = candidate_size - 1 while begin <= end: mid = (begin + end) // 2 if usable_fences[mid] * usable_fences[i] >= X: end = mid - 1 else: begin = mid + 1 # Now the usable_fences[end + 1] is the first qualified # fence. combination_num = candidate_size - (end + 1) num_of_pens += combination_num if num_of_pens > 1000000000: return -1 return num_of_pens |