third minimum

please write a program that receives n numbers from user and prints the third minimum of those,also prints its place.
example:
input:5;
5 7 8 10 6;
output:7,3
thanks

Take all inputs in an array. Copy this array into a new array. Sort this new array. The third minimum element is a[2] (if a is the new array). Find a[2] in the original array to get its position. Naive but ok-ok approach.

2 Likes

I write my code for this question but I dont know what my wrong is.please help me to find my mistake.

#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);// n>=3
int min1,min2,min3;
scanf("%d%d%d",&min1,&min2,&min3);
n -= 3 ;
if (min1>min2)
{
int a;
min1 = a;
min1 = min2;
min2 = a;
}
if(min3 < min2)
{ if(min3 > min1)
{
int b = min3;
min3 = min2;
min2 = b;
}
else
{
int c = min1;
min1 = min3;
min3 = c;
}
}
int i = 0;//i is as counter
while(i < n )
{
int inp;
scanf("%d",&inp);
if(min2 >= inp)
{
int d = min3;
min3 = min2;
min2 = d;
}
if(inp > min2)
{
if(inp < min3)
min3 = inp;
}
i ++;
}
printf(“min3:%d”,min3);
return 0;
}

#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);//because n>=3
int min1,min2,min3;
scanf("%d%d%d",&min1,&min2,&min3);
n -= 3 ;//we get 3num till now
if (min1>min2)
{
int a;
min1 = a;
min1 = min2;
min2 = a;
}
if(min3 < min2)
{ if(min3 > min1)
{
int b = min3;
min3 = min2;
min2 = b;
}
else
{
int c = min1;
min1 = min3;
min3 = c;
}
}
int i = 0;//i is as counter
while(i < n )
{
int inp;
scanf("%d",&inp);
if(min2 >= inp)
{
int d = min3;
min3 = min2;
min2 = d;
}
if(inp > min2)
{
if(inp < min3)
min3 = inp;
}
i ++;
}
printf(“min3:%d”,min3);
return 0;
}


Here is the corrected version of your code along the necessary comments for the corrections -

Here is a better approach -

If u want to find kth smallest element in the array, then i will do in this manner,

procedure: find the first smallest element then mask it,then find the 2nd smallest,mask it and so on…

case1:

 if k<logn

memset(flag,1,sizeof(flag));
cin>>n>>k;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<k;i++)
{
  mini=inf;
  for(j=0;j<n;j++)
  {
    if(flag[j] && mini>a[j])
    {
      mini=a[j];
      x=j;
    }
  }
  flag[x]=0;

}

cout<<mini<<" "<<x;

Time complexity: O(k*n)

case 2: k>logn

Repeat the same procedure for finding (n-k+1)th largest element for the array

Time complexity: O((n-k+1)*n)

In all case better than nlogn sorting…

Note: U can also use my above method to do sorting in O(n^2)… :slight_smile:
Happy coding :slight_smile:

“Here is my problem statement” category identified…

1 Like

@betlista Its ok man :stuck_out_tongue: Newbies :stuck_out_tongue:

please help me to write this program.I am amateur

What if duplicates are present??

No, it’s not ok. This is not related to CodeChef, this user is not solving CodeChef problems, just asking for help for homeworks probably…

sorry,can you help me to write this code?

@pranjalranjan - Why are you sorting ? He is not asking for some k th smallest element so that you need to sort. k = 3 which will be less than log N almost all the times. So instead just find the minimum with an extra variable index and run it through the array 3 times, marking the min element to INT_MAX after each run. O(kn) = O(3n).

@cs_student - no we will not provide you the code for your homework. We gave you the approach, the least you could do is implement it. If your implementation is having problems, we are here to help.

sorry betlista,may you tell me how I can ask my problem so?

it is not my homework,it is one of my problems in my book that I am not able to solve this.it is just for myself

You want me to believe that ?
Show us what have you done so far ? What was your approach ?

1 Like

@thezodiac1994 :- Manipulating variables and explaining to you might be easy for me. But considering the level of the programmer from the type of the code asked, i thought it wise enough to give him the easiest approach so that he can apply the optimization himself.

@vinayawsm :- Always looking for edge cases, are we? :stuck_out_tongue:

@betlista :- I never wrote the code if u noticed. I gave him a very naive approach so that he can develop the rest on his own. Maybe homework, but will help him in the future.

Programming has two parts 1.) figure out the solution 2.) implement the solution. We’d like to know where are you stucked, to help you better…

My problem is process of solving

Then you aren’t stuck at all, because there’s no idea behind this. Figure out how you’d do that the simplest if you had the numbers written on paper, all that’s left is making the program do the same.

1 Like