1<<-DOC
 2You have two integer arrays, a and b, and an integer target value v.
 3Determine whether there is a pair of numbers, where one number is taken from a and the other from b, that can be added together to get a sum of v.
 4Return true if such a pair exists, otherwise return false.
 5
 6Example
 7
 8For a = [1, 2, 3], b = [10, 20, 30, 40], and v = 42, the output should be
 9sumOfTwo(a, b, v) = true.
10
11Input/Output
12
13[time limit] 4000ms (rb)
14[input] array.integer a
15
16An array of integers.
17
18Guaranteed constraints:
190 ≤ a.length ≤ 105,
20-109 ≤ a[i] ≤ 109.
21
22[input] array.integer b
23
24An array of integers.
25
26Guaranteed constraints:
270 ≤ b.length ≤ 105,
28-109 ≤ b[i] ≤ 109.
29
30[input] integer v
31
32Guaranteed constraints:
33-109 ≤ v ≤ 109.
34
35[output] boolean
36
37true if there are two elements from a and b which add up to v, and false otherwise.
38DOC
39
40describe "sum_of_two" do
41  # time: nlogn
42  def sum_of_two(a, b, v)
43    outer, inner =  a.size > b.size ? [b.sort, a.sort] : [a.sort, b.sort]
44    outer.any? { |i| inner.bsearch { |x| (v - i) <=> x } }
45  end
46
47  # time: n
48  def sum_of_two(a, b, v)
49    hash = {}
50    a.each { |x| hash[x] = true }
51    b.any? { |x| hash[v - x] }
52  end
53
54  def sum_of_two(a, b, v)
55    (a.map { |x| v - x } & b).size > 0
56  end
57
58  [
59    { a: [1, 2, 3], b: [10, 20, 30, 40], v: 42, expected: true },
60    { a: [1, 2, 3], b: [10, 20, 30, 40], v: 50, expected: false },
61    { a: [], b: [1, 2, 3, 4], v: 4, expected: false },
62    { a: [10, 1, 5, 3, 8], b: [100, 6, 3, 1, 5], v: 4, expected: true },
63    { a: [1, 4, 3, 6, 10, 1, 0, 1, 6, 5], b: [9, 5, 6, 9, 0, 1, 2, 1, 6, 10], v: 8, expected: true },
64    { a: [3, 2, 3, 7, 5, 0, 3, 0, 4, 2], b: [6, 8, 2, 9, 7, 10, 3, 8, 6, 0], v: 2, expected: true },
65    { a: [4, 6, 4, 2, 9, 6, 6, 2, 9, 2], b: [3, 4, 5, 1, 4, 10, 9, 9, 6, 4], v: 5, expected: true },
66    { a: [6, 10, 25, 13, 20, 21, 11, 10, 18, 21], b: [21, 10, 6, 0, 29, 25, 1, 17, 19, 25], v: 37, expected: true },
67    { a: [22, 26, 6, 22, 17, 11, 9, 22, 7, 12], b: [14, 25, 22, 27, 22, 30, 6, 26, 30, 27], v: 56, expected: true },
68    { a: [17, 72, 18, 72, 73, 15, 83, 90, 8, 18], b: [100, 27, 33, 51, 2, 71, 76, 19, 16, 43], v: 37, expected: true },
69  ].each do |x|
70    it do
71      expect(sum_of_two(x[:a], x[:b], x[:v])).to eql(x[:expected])
72    end
73  end
74
75end