Problem:
Given an integer 'k' and an sorted array A (can consist of both +ve/-
ve nos), output 2 integers from A such that a-b=k.
PS:
nlogn solution would be to check for the occurence of k-a[i] (using
binary search) when you encounter a[i]. methods like hash consume
space.
Is an O(n) solution with O(1) extraspace possible?
My code:
main()
{
int array[] = {6,4,3,1,0,-1};
int n=6;
int target=5;
int diff;
int left=0;
int right=1;
while ( left != n && right != n ) // left< right) // or should the
condition be
{
diff=array[left]-array[right];
if (diff > target)
{
left++; right++; // check for end condition
}
else if(diff == target)
{
printf("%d %d\n",array[left],array[right]);
left++;right++;
}
else
{
right++;
}
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
