CareerCup

public static void findAllPossibleBetter(int [] array, int target){
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();

for (int i=0;i<array.length;++i){
if (map.containsKey(array[i])){
System.out.println(map.get(array[i])+":"+i);
}else{
int dif=target-array[i];
map.put(dif, i);
}
}

}

If extra space is not available, use a in-place O(nlogn) sort algorithm to sort the array. Have two pointers left, right that increase/decrease if current total is smaller/larger than target.

O(nlogn) space O(1)

<pre lang="" line="1" title="CodeMonkey91480" class="run-this">class Main
{
public static void hashMethod2(int[] arr, int sum) {

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

boolean found = false;
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length; ++i) {
Integer temp = map.get(sum - arr[i]);
if (temp == null) {
map.put(arr[i], i);
} else {
found = true;
System.out.println(String.
format("Given sum %d, found %d at index %d and %d at index %d.", sum,
arr[i], i, sum - arr[i], temp));
}
}
if (!found) {
System.out.println(String.format("Given %d, no solution is found.", sum));
}
}

public static void main(String[] args) {
int[] arr = { 1, 2, 13, 34, 9, 3, 23, 45, 8, 7 };
hashMethod2(arr, 11);
}
}</pre>

how abt this??

1. store in harsh table
2. for element i (0 to n)... look in to harsh for element (target - a[i])....

a look up will tale O(1) for n look up complexity is O(n)

Use hash table or another array.

go thru the arraylist and compute the difference between the target sum (e.g. 11) and the current member of the list you are lookng at. store that difference in hash or array storage, and also store the index from the original list in which this difference is obtained.

When done (thru the arraylist), do a search in the hash or storage for members in the arraylist that matches the difference. If found, you have the two indexes you need- one stored in the hash/storage, the other is the search result index.

This should be O(n).

that only works when numbers are positive.

sort the array in O(nlogn) time , and then use binary search . O(nlogn) complexity .

int arr[5]={11,24,10,30,4};
int target=41;
int i=0;
int j=0;
for(i=0;i<5;i++)
{
int number = arr[i];
for(j=i+1;j<5;j++)
{
int number2= arr[j];
if(target==number+number2)
{

printf("\n-----------------");
printf("\n 1st number %d",arr[i]);
printf("\n 1st number index %d",i);
printf("\n 2nd number %d",arr[j]);
printf("\n 2nd number index %d",j);
printf("\n-----------------");
}

}
}


getchar();

The algorithm below finds 1 pair. However, it can be easily worked to find all possible pairs. Also it return 1 or -1 depending on whether any required pair exists or not. Users can work it to return indexes

hasArrayTwoCandidates (A[], ar_size, sum)
1) Sort the array in increasing order.
2) Initialize two index variables to find the candidate
elements in the sorted array.
(a) Initialize first to the leftmost index: l = 0
(b) Initialize second the rightmost index: r = ar_size-1
3) Loop while l < r.
(a) If (A[l] + A[r] == sum) then return 1
(b) Else if( A[l] + A[r] < sum ) then l++
(c) Else r--
4) No candidates in whole array - return -1

int check_sum(int a[],int n,int k){
	sort(a,n);                     //o(nlogn)
	int left=0,right=n-1;
	while(left<right){
		if(a[left]+a[right]==k)
			return 1;
		else if(a[left]+a[right]>k)
			right--;
		else
			left++;
	}
	return 0;
}