Programming Assignment 3 Sum of two numbers Naively we can t

Programming Assignment

3 Sum of two numbers Naively we can try for every element z in the array look at the other elements in the array and check if one of them is u 2. This algorithm takes O(n2) time. A better algorithm with O(nlogn) time is possible. We first sort the array A in O(nlogn) time (using merge sort, for example). Now, for every element 2 in the array check if the array has u z as another element. Tis can be done using binary search. For every element of the array, searching takes O(logn) time. Thus the run time of the entire algorithm is O(nlogn).

Solution

Brute Force

isSumPossible ( int [] arr, int len, int sum) {

int sumRemaining = sum;

for (int i =0; i< len; i++) {

sumRemaining = sum - arr[i];

for (int j =0; j<len; j++) {

if (sumRemaining == arr[j]) {

//sum is possible

return 1;

}

}

}

Optimized

isSumPossible ( int [] arr, int len, int sum) {

Arrays.sort(arr);

int sumRemaining = 0;

sumRemaining = sum - arr[i];

for (j=0;j<len;j++) {

if(sumRemaining == arr[j]) {

return 1;

} else if(sumRemaining < arr[j]) {

//this sum cannot exist as all items on right of j are greater

return 0;

} else {

continue;

}

}

}

}