-
Notifications
You must be signed in to change notification settings - Fork 0
/
ctci-ice-cream-parlor.py
63 lines (47 loc) · 1.42 KB
/
ctci-ice-cream-parlor.py
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
"""
Binary Search: Ice Cream Parlor
https://www.hackerrank.com/challenges/ctci-ice-cream-parlor
"""
import unittest
def solve(m, arr):
len_arr = len(arr)
arr_idx = [(arr[idx], idx + 1) for idx in range(len(arr))]
sorted_arr = sorted(arr_idx)
for item, idx in sorted_arr:
pair = m - item
left = 0
right = len_arr
mid = int(len_arr / 2)
while left < mid < right:
mid_value = sorted_arr[mid][0]
if mid_value == pair:
return sorted([idx, sorted_arr[mid][1]])
if mid_value > pair:
right = mid
mid = int((left + mid) / 2)
elif mid_value < pair:
left = mid
mid = int((mid + right) / 2)
if __name__ == '__main__':
t = int(input().strip())
for a0 in range(t):
m = int(input().strip())
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
answer = solve(m, a)
print(answer[0], answer[1])
class TestSolve(unittest.TestCase):
def test_solve(self):
answer = solve(8, [2, 1, 9, 4, 4, 56, 90, 3])
self.assertEqual(
[4, 5],
answer
)
answer = solve(
295,
[678, 227, 764, 37, 956, 982, 118, 212, 177, 597, 519, 968, 866, 121, 771, 343, 561]
)
self.assertEqual(
[7, 9],
answer
)