CareerCup

max and second maxinum can be found in just O(n).
here is the code.

#include<iostream>
using namespace std;
int main()
{
vector<int> v;
int array[]={0,4,1,8,2,3,7,5,6};
int max1=0,max2=0;
for(int i=0;i<9;++i)
{
if(max1<array[i])
max1=array[i];
if(max2<array[i]&&array[i]<max1)
max2=array[i];
}
cout<<max1<<" "<<max2<<"\n";
system("pause");
return 0;
}

sorry for vector<int> v. it's not needed

simple code for the second largest value.

#include "stdio.h"
#include<conio.h>
using namespace std;
int main()
{
    int a[10] = { 11, 2, 9, 13, 33, 25, 17, 1, 90, 3 } ;
    int fmax = 0; int smax = 0;
    for(int i=0; i<10;i++)
    {
      if(a[i]>fmax)
      {
      smax=fmax;
      fmax=a[i];
      }
      else if (smax<a[i])
           smax = a[i];                 
     }     
     printf("%d, %d", fmax, smax);
     getch();
     return 0;
}

We can sort using some O(nlogn) algorithm like heapsort by making a maxheap and find the max number .

Sorting is not required if we have to find just the maximum or minimum number. Here's how we can achieve that:
1. Have two var - max, min - initialized to the first element.
2. Compare each subsequent element with max and min.

if (a[i]>max)
max=a[i];
else if (a[i]<min)
min=a[i];

Max: n-1.
Max + second Max: n + logn -1.

Take two variables max, secondMax and iterate the array initializing both to the first element. if an item is greater than max then update secondMax to max to new max value. If the item is greater than secondMax, update secondMax to that value. When all items are enumerated, secondMax shall contain secondMax value.

the whole problem of finding largest and second largest element can be found out by (n+logn) steps.
Here is the procedure:

First make all the elements of the array as leaf nodes. consider pair of elements and make the larger one as the parent and continue further until u get a single element which is largest.

Now that we got the largest element in (n/2) + (n/4) + . . . + 1 = (n - 1) steps
and also we have build a binary tree...

Now the second largest element should be somewhere compared with the largest element as it would become the parent with every other element except with the largest.

Thus by following the comparisions of the largest element along the branch we can find the second largest element in (log n) steps...

Please correct me if I am wrong.

the whole problem of finding largest and second largest element can be found out by (n+logn) steps.
Here is the procedure:

First make all the elements of the array as leaf nodes. consider pair of elements and make the larger one as the parent and continue further until u get a single element which is largest.

Now that we got the largest element in (n/2) + (n/4) + . . . + 1 = (n - 1) steps
and also we have build a binary tree...

Now the second largest element should be somewhere compared with the largest element as it would become the parent with every other element except with the largest.

Thus by following the comparisions of the largest element along the branch we can find the second largest element in (log n) steps...

Please correct me if I am wrong.

How do you code it?

<pre lang="" line="1" title="CodeMonkey38946" class="run-this">#include<iostream.h>



int main()
{
int a[10],i,j,max,sec; // creates as many ints as necessary
for (i = 0; i <10; i++)
{
cin >> a[i];
// until the array is full
}
max=sec=a[0];

for (int j =1; j <10; j++) // loop to print the stars for each array

{
if(a[j]>max)
{sec=max;
max=a[j];
}
else if(a[j]>sec)
sec=a[j]; // value


}

cout<<sec<<endl;
getch();
return 0;

}

</pre><pre title="CodeMonkey38946" input="yes">
</pre>

sorry for vector<int> v. it's not needed

Tournament tree -> if both max, and 2nd max are required -> O(n + logn)
nth largest element -> quickSelect -> O(n)

1) Make a Mx-heap from the given array
2) O(1) to get the Max number.
3) Second largest element is one of the child of root node of heap.
4) Only one comparison is needed to find the second largest number

#include<iostream>
using namespace std;
int main() {
	int n,i;
	cout << "Enter the size of array: ";
	cin  >> n;
	
	int a[n];
	cout<<"\nEnter the elements in array: \n";
	for(i=0;i<n;i++) cin>>a[i];

	int f=0;
	int s=1;

	if(a[s]>a[f]){
		int temp=f;
		f=s;
		s=temp;
	}

	for(i=1;i<n;++i) {

		if( (a[i]>a[f]) && (a[i] > a[s]) ) {
			s=f;
			f=i;
		}
		if(a[i]<a[f] && a[i]>a[s] )
			s=i;
	}
	cout<<"\nSecond highest: "<<a[s]<<endl;
	
	return 0;
}

/*max and second maxinum can be found in just O(n).*/

#include<iostream>
using namespace std;
int main()
{
int n,i;
cout << "Enter the size of array: ";
cin  >> n;
int a[n];
cout<<"\nEnter the elements in array: \n";

for(i=0;i<n;i++) cin>>a[i];
int f=0;
int s=1;
if(a[s]>a[f])
{
int temp=f;
f=s;
s=temp;
}
for(i=1;i<n;++i)
{
if( (a[i]>a[f]) && (a[i] > a[s]) )
{
s=f;
f=i;
}
if(a[i]<a[f] && a[i]>a[s] )
s=i;
}
cout<<"\nSecond highest: "<<a[s]<<endl;
cout<<"\nFirst Highest : "<<a[f]<<endl;
return 0;
}

Finding max min and sec_max in O(n) time

#include <iostream>
#include <stdlib.h>
#define SIZE 50
using namespace std;

int main()
{
int max, min, sec_max,n;
int arr[SIZE];
int i;
cout<<"Enter no. of element\n";
cin>>n;
for(i = 0; i < n; i++)
cin>>arr[i];
if(n > 1)
{
sec_max = arr[0]>arr[1]?arr[1]:arr[0];
}
max = min = arr[0];
for(i = 1;i < n; i++)
{
if(arr[i] > max)
{
sec_max = max;
max = arr[i];
}
if(arr[i] < min)
min = arr[i];
}
cout<<max<<" "<<sec_max<<" "<<min;
getchar();
return 0;
}

Couldn't comment to @nihaldps so writing a new post.

fmax --maximum element in the array.
smax --second maximum element in the array.

Your solution fails for all negative elements in the array. So always initialise fmax and smax with a[0].

Suppose,a[0] is the greatest element in the array then,the number of comparisions that your code does is 2(n-1).Since from index=1 to n-1 every element will be compared to fmax and then to smax also.

This question can have a better solution.

We can find the fmax in n-1 comparisions.
For finding the second maximum element, we are sure that at any point of time second maximum element should have been compared with maximum element.So if somehow we can keep information that which all elements have been compared with maximum elements. We can find maximum of those which would be the second maximum element.


Prepare a decision tree as follows,
Compare a0 with a1, a2 with a3, a4 with a5......and so on.
then keep on going with winners among those.
We come to know that number of elements which get compared with maximum element is log(n) ------height of decision tree.
So now we can compute max from these in log(n)-1 comparisions.

So total no. of comparisions= n-1+log(n)-1=n+logn-2

We can use the divide and conquer method (Tournament Method) to find the maximum and second maximum in O(n) time

we can do both in jus N-1 steps:
int large=0,sec_large=0;
for(i=0;i<N;i++)
if(arr[i]>large)
{ small=large;
large=arr[i];
}
else if(arr[i]<large&& arr[i]>sec_large)
sec_large=arr[i];


}

public class ThirdLargestNumber {
public static void main(String[] args) {
int arr[] = { 200, 200, 100, 100, 300,600 };
int first = 0, second = 0, third = 0, temp = 0, temp1 = 0;
for (int i = 0; i <= 5 /*
* Length of array-1. You can use here length
* property of java array instead of hard coded
* value
*/; i++) {

if (arr[i] == first) {
continue;
}
if (arr[i] > first) {
temp = first;
temp1 = second;
first = arr[i];
second = temp;
if (temp1 > third) {
third = temp1;
}
} else {
if ((arr[i] == second) || (arr[i]) == first) {
continue;
}
if ((arr[i] > second) && (arr[i]) < first) {
temp1 = second;
second = arr[i];
if (temp1 > third) {
third = temp1;
}
} else {
if (arr[i] > third) {
third = arr[i];
}
}
}
}
System.out.println("Third largest number: " + third);
System.out.println("Second largest number: " + second);
System.out.println("Largest number: " + first);
}

}