Question

Write a method public static boolean FindSum (int[] a, int m) that takes an ascending sorted array a with n distinct integers, and an integer m. If there are two elements in the array that add to be m, the method returns True; if not, it returns False. You may assume that the elements in the array are all distinct. There are several ways to solve this problem! (and some solutions are worth more points than others!) For 6 points, write a method that has oin?) runtime. For 9 points, write a method that has on lg n) runtime. For the full 12 points, write a method that has O(n) runtime. You must identify the correct runtime for your code. You will receive credit for the "highest" method that you write correctly, and give the correct time complexity!

Answer 1

#source code in java:

public class Test{

public static boolean FindSum(int[] a,int m){

int least=0;

int high=a.length-1;

while(least<high){

if(a[least]+a[high]==m){

return true;

}

else if(a[least]+a[high]<m) {

least=least+1;

}

else{

high=high-1;

}

}

return false;

}

public static void main(String args[]){

int a[]={1,6,8,9,10,11};

int m=16;

System.out.println(FindSum(a,m));

System.out.println(FindSum(a,24));

}

}

1 2 3 4 5 6 public class Test{ public static boolean FindSum(int[] a, int m) { int least=0; int high=a. length-1; while(least<high) { if(a[least]+a[high]==m) { return true; } else if(a[least]+a[high]<m) { least=least+1; 7 8 } else{ high=high-1; } } return false; 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 } public static void main(String args[]) { int a[]={1,6,8,9,10,11}; int m=16; System.out.println(FindSum(a,m)); System.out.println(FindSum(a, 24)); } 보

The TIme complexity is 0(n) runtime which is best case of the algorithm

#source code output:

user@user-Latitude - 3490:-/Desktop$ javac Test.java user@user-Latitude - 3490:-/Desktop$ java Test true false user@user-Latitude - 3490:-/Desktops |

#if you have any doubt or more information needed comment below..i will respond as possible as soon..thanks.