|
Given a sorted array, find a pair of elements that sum upto a given value.
Microsoft Interview Questions and Answers
(Continued from previous question...)
81. Given a sorted array, find a pair of elements that sum upto a given value.
Question:
Given a sorted array, find a pair of elements that sum upto a given value.
maybe an answer:
int main ()
{
int k[10] = {0}; // hash array to store the potential pairs
int a[] = {1,2,3,4,5,6,7,8,9,10}; // sorted array
int sum =7; // given value to be a sum
int i =0, tmp;
for(i = 0; i < sum; i++)
{
tmp = sum - a[i];
if(k[tmp] != tmp)
{
k[a[i]] = a[i];
printf("k[%d] = %d\n", tmp, k[tmp]);
}
else
{
printf("Pair = {%d, %d}\n", tmp, a[i]);
}
}
return 0;
}
works only with positive numbers in array
maybe an answer2:
int a[] = {1, 3, 5, 6, 8, 10};
int sumToFind = 9;
int i = 0;
int j = (sizeof(a)/sizeof(a[0])) - 1;
while (i < j) {
int sum = a[i] + a[j];
if (sum == sumToFind) {
cout << i << ", " << j << endl;
break;
}
(sum > sumToFind)? j-- : i++;
}
(Continued on next question...)
Other Interview Questions
| 