5) to find out maximum element in a list of n numbers, one needs at least
Answers
int min;
int max;
};
struct pair getMinMax(int arr[], int n)
{
struct pair minmax;
int i;
/*If there is only one element then return it as min and max both*/
if (n == 1)
{
minmax.max = arr[0];
minmax.min = arr[0];
return minmax;
}
/* If there are more than one elements, then initialize min
and max*/
if (arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.max = arr[1];
minmax.min = arr[0];
}
for (i = 2; i<n; i++)
{
if (arr[i] > minmax.max)
minmax.max = arr[i];
else if (arr[i] < minmax.min)
minmax.min = arr[i];
}
return minmax;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax (arr, arr_size);
printf("nMinimum element is %d", minmax.min);
printf("nMaximum element is %d", minmax.max);
getchar();
}
Answer:
The program and algorithm is constructed.
Step-by-step explanation:
One of the simplest algorithm is to find the largest number in a list of numbers. The solution necessarily requires looking at every number in the list,but only once at each. From the follows a simple algorithm, which can be stated in high level description prose, as:
Assume the first element is largest.
Look at each of the remaining elements in the list and if it is larger than the largest element so far, make a note of it.
The last noted element is the largest in the list when the process is complete.
Above formal description is written in prose but much closer to high-level language of a computer program, the following is the more formal coding of the algorithm in pseudo code or pidgin code:
Algorithm Larger_Number
Input: A non-empty list of numbers L.
Output:The largest number in the list L.
- Largest<-L0
- For each element in the list L >=1, do
- if the element > largest, then
- Largest<- the element
return largest.
Given an integer array, find out the minimum and maximum element present using minimum comparisons.
For example,
Input: nums[] = [5, 7, 2, 4, 9, 6]
Output:
The minimum array element is 2
The maximum array element is 9
Practice this problem
nums naive solution is to compare each array element for minimum and maximum elements by considering a single item at a time. The time complexity of this solution would be linear. The implementation can be seen below in C++, Java, and Python:
Program
#include <iostream>
#include <vector>
using namespace std;
// Naive solution to find the minimum and maximum number in an array
void findMinAndMax(vector<int> const &nums, int &min, int &max)
{
// initialize minimum and maximum element with the first element
max = nums[0], min = nums[0];
// do for each array element
for (int i = 1; i < nums.size(); i++)
{
// if the current element is greater than the maximum found so far
if (nums[i] > max) {
max = nums[i];
}
// if the current element is smaller than the minimum found so far
else if (nums[i] < min) {
min = nums[i];
}
}
}
int main()
{
vector<int> nums = { 5, 7, 2, 4, 9, 6 };
// to store minimum and maximum element, respectively
int min, max;
findMinAndMax(nums, min, max);
cout << "The minimum array element is " << min << endl;
cout << "The maximum array element is " << max << endl;
return 0;
}
The above solution does 2×(n-1) comparisons in the best case and 3×(n-1) comparisons in the worst case. The worst case happens when all array elements are equal or are sorted in descending order. The best case happens when the input is sorted in ascending order. (Note that we have also considered n-1 comparisons done by for-loop).