## Interview Question

Quality Assurance Engineers**Country:**India

**Interview Type:**In-Person

it is a typical question

1. sort the array in ascending order

2. set two pointer i,j:

i point at the first element(also smallest) of the array

j point at the last element(also largest) of the array

3. now move the i to the end of the array and move the j to the begin of the array according to the result r=array[i]+array[j]:

if r>target: set j--

if r<target: set i++

if r == target: you got one pair, if any number can only in one pair you should do both j-- and i++ otherwise its up to you choice

I always disagree with solutions coming out of naive iterations !!!

This can be solved by using Binary Search.

Perform a binary search for SUM - arr[i] in array.

This problem can be solved in three ways:

1)fix one element and find other element such that a[i] + a[j] =9 using linear search;

for(i=1;i<n;i++)

{ for (j= i;j<n; j++)

if(a[i] + a[j]==9)

return(i,j);

}

time complexity= O(n2)

2) fix first element and find other by binary search

for(i=1;i<n;i++)

{ use binary search here.

}

time complexity= O(nlogn)

3)

use greedy technique

take two pointers p1,p2 put them at rear ends.

then

if(a[p1] + a[p2] =9 )

return element at address;

otherwise

if(a[p1] +a[p2]> 9)

p2--;

elseif(a[p1] +a[p2]<9)

p1++;

time complexity= O(n)

#include<iostream>

#define MAX 7

int main(int argc,char **argv)

{

int arr[MAX]={0,4,2,3,5,6,9};

int com_num;

int end_index=MAX-1;

int index,sum=0;

std::cout<<"Enter commbination number"<<std::endl;

std::cin>>com_num;

for(index=0; index<MAX-1;)

{

sum=arr[index]+arr[end_index];

if(sum==com_num)

{

std::cout<<"{"<<arr[index]<<","<<arr[end_index]<<"}"<<"\t";

}

end_index--;

if(end_index==index)

{

index++;

end_index=MAX-1;

}

}

}complexity o(n)

```
def printCombination(numList, summ):
numDict = {}
for num in numList:
partner = summ - num
if partner in numDict:
print "(%i, %i)" %(num, partner)
else:
numDict[num] = Truedef printCombination(numList, summ):
numDict = {}
for num in numList:
partner = summ - num
if partner in numDict:
print "(%i, %i)" %(num, partner)
else:
numDict[num] = True
```

The question is similar to find pairs that sum up to a given number. This problem can be solved in O(n) as:

- vgeek September 22, 2013