Given an integer array A and an integer k$,$ we want to find all pairs of elements in the array that add up to k$.$ For each pair found, print the two numbers. If it is not possible to find any such combination, print "Not possible." The elements in A are unique. The array elements and k could be positive, zero, or negative. You do not need to print the other permutation that represents the same pair.

Sample Run $1$

Enter size of array: $10$

Enter the elements: $25611-1025-318$

Enter the value of k: $22$

$-325$

Sample Run $2$

Enter size of array: $10$

Enter the elements: $25611-1025-318$

Enter the value of k: $50$

Not possible.

There are two $($to four$)$ algorithms to solve this problem. One is a brute force algorithm, while the others are more efficient but require more code to implement. Design and analyze the big$-$O time complexity of two algorithms, then implement them.

public void findPairsBruteForce$($int$[]$ input, int target$)\{$

$\}/*$ TODO $*/$

public void findPairsImproved$($int$[]$ input, int target$)\{$

mergeSort$($input$)$; $//$ O$($n log n$)$ sort given to you

$//$ Efficiency should be better than the brute force algorithm! $\}$