Given array and a number x, check for pair in arr with sum x

We can directly jump to brute force approach and end up with o(n2) complexity solution.










No. comparisons = ( n(n+1) / 2 ) - n where n is array length.

Problem with above approach are
a. Trying unnecessary combinations
    means more comparisons,add operations,time consumption etc
b. Giving interviewer one chance to reject us :)

Better approach 1:

Whenever we are dealing with arrays, following things, we need to keep in mind

1) Array sorting.
2) Input range.
3) minimum no.of comparisons/copy operations needed.
4) Usage of index pointers
5) Boundary conditions (<arr.length , >-1)

Most of the times, sorting and binary search combination solves most of the array problems for us.

Best thing about this approach is, we are avoiding unnecessary combinations by taking advantage of sorted data.

If we find, summation is less than X, then we should try adding next big number from beginning otherwise try adding next small number from ending.

This solution works in o(nlogn) sorting + o(n) time which is way better than o(n2).

Best apporach 2:

If there is no constraint on extra space, then we can try out below approach.

Note1: We should know range of input
Note2: This solution works for negative numbers as well !

Above approach does the trick in o(n) complexity with additional space.

Above approach works like a charm, while dealing with negative numbers. All we have to do is try converting all -ve numbers into positive ones.

     int[] arr = new int[]{1,4,45,-6,10,-8};
     int x = 2

Steps:
a) Find least minimum number and it's absolute value: |-8| = 8
b) Add 8 to all input values: {9,12,53,2,18,0}
c) Add 8 + 8 to x: 16 +2 = 8

10 + (-8) = 2
(10 + 8) + -8 = 10;
18+ -8+8 = 10+8
18 = 18

Hope you find this post useful.

Happy learning :)