Two independent relay networks have been strung along the same frontier line. The first network has n towers and the second has m towers, every tower placed at an integer coordinate on the line. Two towers interfere with each other whenever the distance between their coordinates is at most a given threshold d. Count how many towers belonging to the first network are completely free of interference — that is, farther than d from every single tower in the second network.
Print a single integer: the number of first-network towers with no interference from any second-network tower.
Example 1
Input
3 4 2 4 5 8 10 9 1 8
Expected
2
Explanation
For 4: distances to 10, 9, 1, 8 are 6, 5, 3, 4, all greater than d=2, so 4 is isolated. For 5: distances are 5, 4, 4, 3, all greater than 2, so 5 is isolated too. For 8: the distance to 8 in the second array is 0, which is not greater than 2, so 8 is not isolated. That gives 2 isolated towers, so the output is 2.
Example 2
Input
4 6 3 1 4 2 3 -4 -3 6 10 20 30
Expected
2
Explanation
For 1: the smallest distance to any second-array value is |1-(-3)|=4 or |1-6|=5, both greater than d=3, so 1 is isolated. For 4: |4-6|=2, which is not greater than 3, so 4 is not isolated. For 2: the closest second-array values give |2-6|=4 and |2-(-3)|=5, both greater than 3, so 2 is isolated. For 3: |3-6|=3, which is not greater than 3, so 3 is not isolated. That gives 2 isolated towers (1 and 2), so the output is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →