Please do problem 3 In this problem, we are given a sequence a_1, a_2, .. ., a_n
ID: 3781603 • Letter: P
Question
Please do problem 3
In this problem, we are given a sequence a_1, a_2, .. ., a_n of integers and we want to return a list of all terms in the sequence that are greater than the sum of all previous terms of the sequence. For example, on an input sequence of 1, 4, 6, 3, 2, 20, the output should be the list 1, 4, 6, 20. The following algorithm solves this problem. procedure PartialSuins(a_1, a_2, .. ., a_n: a sequence of integers with n greaterthanorequalto 1) total:= 0 Initialize an empty list L. for i:= 1 to n if a_i > total Append a_i to list L. total:= total + a_i return L Prove the following loop invariant by induction on the number of loop iterations: Loop Invariant: After the t^th iteration of the for loop, total = a_1 + a_2 +. .. + a_t and L contains all elements from a_1, a_2, .. ., a_t that are greater than the sum of all previous terms of the sequence. Use the loop invariant to prove that the algorithm is correct, i.e., that it returns a list of all terms in the sequence that are greater than the sum of all previous terms of the sequence.Explanation / Answer
import java.lang.*;
import java.util.Scanner; //reading from console
class TestSum{
public static void main(String[] args){
Scanner s = new Scanner(System.in);
System.out.println("Enter the size of array");
int[] arr = new int[s.nextInt()];
System.out.println("Enter the numbers");
for(int i=0;i<arr.length;i++){
if(s.hasNextInt()){
arr[i] = s.nextInt(); // input array = [1,4,6,3,2,20]
}
}
partialSums(arr);
}
public static void partialSums(int[] arr){
int[] output = new int[arr.length]; //output arrey
int k=0; //output array's initial size
for(int i=0;i<arr.length;i++){
int sum = 0;
for(int j=0;j<i;j++){ //this loop is to sum all the previous elements of an array
sum += arr[j];
}
if(sum<arr[i]){ //if it is true then put it in output array
output[k++] = arr[i];
}
}
if(k!=0){ // print the output array = 1,4,6,20
System.out.print("Output List of numbers = ");
for(int i=0;i<k;i++){
System.out.print(output[i]+" ");
}
}else{
System.out.println("No number is greater than the sum of its previous numbers");
}
}
}