CareerCup

The code is

#include<stdio.h>
#include<stdlib.h>
/* 
   Assume the array is in reverse sort order...
   { 15, 14, 13, 12, 11, 8, 3, 1 }
*/

void FindSum(int* arr, int len, int sum)
{
  int i=0,j=len-1;
  int diff = 0 ;
  while ( i < j )
  {
    if ( arr[i] + arr[j]  < sum )
    {
      j--;
    }
    else if ( arr[i] + arr[j] > sum )
    {
      i++;
    }
    else
    {
      printf("%3d(%d) + %3d(%d) = %3d\n",arr[i],i,arr[j],j,sum);
      return ;
    }
  }
  printf("Go Away!\n");
}
int main(int argc, char** argv)
{
  int i ;
  int* arr;
  int sum = 0 ;
  arr = (int*)malloc(sizeof(int)*(argc-2) );
  sum = atoi(argv[argc-1]);
  for ( i = 1 ; i < argc -1; i++)
  {
    arr[i-1] = atoi(argv[i]);
  }
  FindSum(arr,argc-2,sum);
}

/***
~/Codes$ ./a.out 15 14 13 12 11 8 3 1 24
13(2) + 11(4) = 24
~/Codes$ ./a.out 15 14 13 12 11 8 3 1 4
3(6) + 1(7) = 4


*/

suppose array A[0...N)
For i = [0, N)
IF Min<=(givenValue-A[i])<=Max
IF BinarySearch(givenValue-A[i]) is true
Print pair

O(NlgN)

int findval(int *arr,int len,int val)
{
	if(len=2)return 0;
	int half=len/2;
	if((arr[half]+arr[half-1])<val)
		return half+findval(arr+half,len-half,val);
	else if(half>1&&arr[half-1]+arr[half-2]>=val)
		return findVal(arr,half,val);
	else
		return half-1;
}

you can find out first element in O(log(n!)),take first element say s make binary search for (value-s) on n-1 elements then take second one say s1 & make binary search for (value-s1) on n-2 elements & so on ....hence it would be best with O(log(N)) & worst with O(log(n!)).

generally we talk about worst case complexity and o(log(n!)) is a very complex algorithm.
simple one can be like this with order o(n).
assuming increasing order of list.left anr right are leftmost and rightmost indices.

if((left+right)<sum)
left++;
else if((left+right)>sum)
right--;
else return(left,right)

it has best case O(1) complexity.

was wondering if we can use maps here.. that would not use the fact that the given array is sorted.. comments ?

First sort the array and then take each element and use binary search to find the value of sum-array_element_value. Time Complexity O(n lg n)