Count Distinct Pairs Summing to K

Given an array of integers and a target integer \( k \), your task is to count the number of distinct pairs \( (i, j) \) such that \( i < j \) and \( arr[i] + arr[j] = k \). The array may contain negative numbers and duplicate elements, so be sure to handle these cases efficiently.

For example, if \( arr = [1, 2, 3, 4, 3] \) and \( k = 6 \), there are exactly two valid pairs: \( (2, 4) \) and \( (3, 5) \) (using 1-indexed positions). Your solution should be optimized to work for larger inputs as well.

inputFormat

The input is read from standard input (stdin) and consists of three lines:

1. The first line contains an integer \( n \), representing the number of elements in the array.
2. The second line contains \( n \) space-separated integers, the elements of the array \( arr \).
3. The third line contains an integer \( k \), the target sum.

outputFormat

Output a single integer on standard output (stdout): the number of distinct pairs \( (i, j) \) such that \( i < j \) and \( arr[i] + arr[j] = k \).

5
1 2 3 4 3
6

2