Programming Assignment 3 Sum of two numbers Naively we can try for every element
ID: 3787880 • Letter: P
Question
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).Explanation / Answer
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;
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.