517. Count Pairs in Two Sorted Arrays Whose Sum is K

Given two sorted arrays a and b and a target k, count the number of pairs (i, j) such that a[i] + b[j] equals k. Use binary search over the second array. The input is JSON {a, b, k}. Return the count.

Input: JSON {a, b, k}.

Output: Integer — the number of pairs summing to k.

Examples

Input: {"a":[1,2,3,4],"b":[1,2,3,4],"k":5}
Output: 4
Explanation: (1,4),(2,3),(3,2),(4,1).

Input: {"a":[1,1,1],"b":[1,1,1],"k":2}
Output: 9
Explanation: All nine pairs sum to 2.

Input: {"a":[1],"b":[5],"k":6}
Output: 1
Explanation: One matching pair.

Constraints

• 1<=len(a),len(b)<=10^4
• sorted ascending

Asked by