ORIGINAL CODING QUESTION

Pair a mentoring budget

Count index pairs i < j whose activity costs add to the target budget. Equal values at different indexes count separately.

Open practice workspace

Original exercise · medium. Editorial role relevance does not imply a company has asked this question.

Input and output

n, then n costs, then target. Print the number of index pairs.

Constraints

1 ≤ n ≤ 10,000; costs and target are between -100,000 and 100,000.

Example 1

Input

4
1 3 2 2
4

Output

Pairs (1,3) and the two distinct 2s produce two pairs.

Example 2

Input

3
2 2 2
4

Output

All three index pairs qualify.

Explain your approach

Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?

Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.

Hint 1

Counting frequencies handles duplicates.

Hint 2

For each cost, ask how many earlier costs equal target minus cost.

Hint 3

Add the complement frequency before incrementing the current cost frequency.

Practice this question

Save your work privately, explain decisions and return to your revision queue.

Open practice workspace Browse the question library →