Question

LargestTwo problem: Based upon the pseudocode code below, implement in C++ a divide-and-conquer algorithm that finds the largest and second largest value from a vector of ints.

void LargestTwo (vector l, int left, int right, int & largest, int & secondLargest)

• Please write comment for your functions, similar to the one in the pseudocode, to include both pre- and post-conditions.

• Comment on the logic of your code, e.g., what is true after the two recursive calls?

• Answer the three questions in the comment of your code. •

Test the function in main(), by calling the function to find out largest and second largest values in a vector of length 2, 3 and 4, and make sure you include cases where the largest and second largest values are the same, e.g., for vector {3,4,4}, the top two largest values are both 4.

Pseudocode

/* return largest and second largest element in list l[left...right] precondition: left+1<=right, i.e., the list contains at least two elements postcondition: the largest and secondLargest will be set to the largest element and second largest element respectively */

LargestTwo (l[], left, right, largest, secondLargest)

{ //Write base case(s) and solutions here if (left+1==right) //i.e., there are two elements in the list

//Fill in the blank else

if (left+2==right) //i.e., there are three elements in the list

//Fill in the blank, i.e., try to set largest, secondLargest

// to the largest and secondLargest values in l[left...right]

mid = (left+right)/2

LargestTwo (l, left, mid, leftL, leftSL)

LargestTwo (l, mid+1, right, rightL, rightSL)

//Fill in the rest of the code

// Note that based upon the postcondition of LargestTwo, we have

// leftL and leftSL are largest and secondLargest value from l[left...mid] // rightL and rightSL are largest and secondLargest value from l[mid+1...right] }

Answer 1

c++ Code:

#include<bits/stdc++.h>
using namespace std;

//function the LargestTwo
void LargestTwo (vector<int> l, int left, int right, int & largest, int & secondLargest)
{
// base cases
if (left+1 == right) //i.e., there are two elements in the list
{
int a = max(l[left], l[right]);
int b = min(l[left], l[right]);
if(max(a, b) > largest)
{
secondLargest = max(largest, min(a, b));
largest = max(a, b);
  
}
else if(max(a, b) == largest)
{
secondLargest = largest;
}
else if(max(a, b) > secondLargest)
secondLargest = max(a, b);
return;
}
else if (left+2==right)
{
int arr[] = {l[left], l[left+1], l[right]};
sort(arr, arr+3);
int a = arr[2];
int b = arr[1];
if(max(a, b) > largest)
{
secondLargest = max(largest, min(a, b));
largest = max(a, b);
  
}
else if(max(a, b) == largest)
{
secondLargest = largest;
}
else if(max(a, b) > secondLargest)
secondLargest = max(a, b);
return;
}
int mid = (left+right)/2;
LargestTwo (l, left, mid, largest, secondLargest);
LargestTwo (l, mid+1, right, largest, secondLargest);
  
}
//main function
int main()
{
int N;
cout << " enter the size:";
cin>>N;
cout <<" enter the elements: ";
vector<int >v(N);
for(int i = 0; i< N; i++)
cin>>v[i];
int largest = INT_MIN, secondLargest = INT_MIN;
LargestTwo(v, 0, N, largest, secondLargest);
cout<<"the largest:"<<largest<<"\nthe secondLargest:"<<secondLargest;
}

Output:

if u like my answer then please give a thumbs up..!!