Loading...
Loading...
Loading...
A hostel warden has n student IDs written in a list, in no particular order. For a lucky draw, she wants two different positions in the list whose IDs add up to exactly T. An ID can be negative, because test entries use negative numbers.
Print the two positions i and j (1-based, i < j). If several pairs work, choose the one with the smallest j. If several pairs have that j, choose the smallest i. If no pair works, print -1.
-1.Example 1
Input
5 9 2 7 11 15 1
Output
1 2
2 + 7 = 9, at positions 1 and 2.
Example 2
Input
4 10 3 3 9 7
Output
1 4
Both 3s pair with the 7 at position 4. The rule picks the smaller position, 1.
Try the problem first. Open one hint at a time.
Checking every pair takes about n²/2 steps, which is 5 × 10^9 when n = 10^5.
Walk through the list once. At position j, the partner you need is T minus the ID at j.
Store each ID with its first position in a HashMap, and look up the partner before you add the current ID.
Look up first, then add: that way the same position is never used twice, and the first pair you find has the smallest j.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor