Loading...
Loading...
Loading...
A college quiz uses negative marking, so a score can be below zero. The quiz club has the scores of n students and a number k.
A pair is two scores x and y from the list with y − x = k. Count how many different pairs of values exist. A pair is counted once, even if its scores appear many times. When k = 0, the pair (x, x) counts only if x appears at least twice.
Example 1
Input
5 2 3 1 4 1 5
Output
2
The pairs are (1, 3) and (3, 5). The second 1 does not make a new pair.
Example 2
Input
5 0 1 3 1 5 4
Output
1
Only 1 appears twice, so (1, 1) is the one pair.
Try the problem first. Open one hint at a time.
For a fixed score x, the only partner that works is x + k. So the question for each x is: is x + k in the list?
Checking "is it in the list" by scanning the whole list each time is O(n²). A structure with fast lookup makes it O(1) on average.
Store how many times each score appears in a HashMap. Then walk over the keys, not the original list, so repeats are counted once.
k = 0 is special: x + 0 is x itself, so count the keys whose count is at least 2. Keep x + k in a long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor