Header Ads Widget

The Magical Mountain | Hackerearth practice problem solution

Rajnish Tripathi 09:20

 Problem:-

Armenia and Azerbaijan are in a state of war. Both these countries are separated by a long stretch of mountains of unequal heights. Each country sends its soldiers on the border and these soldiers will have to take position on one of the mountain i.e. 2 mountains will be occupied by two different armies. Uzairovic is a Russian who is acting as a double spy. He asks the Armenians to choose their mountain before the other army chooses theirs but he places two conditions:

1.Armenia will have to march forward and choose a mountain which is largest in height as compared to all the moutains which they have encountered up till now. But in this way, they can choose more than one mountain. So to avoid this, Uzairovic places another condition:

2.Armenia will have to choose the mountain which is the median of all the possible choices from condition 1.

The Armenians are very happy and thank Uzairovic for giving them the advantage of choosing the mountain first. But they don’t know that Uzairovic has planned to plant a bomb in the mountain which will be choosen by Armenia before they arrive there. Help Uzairovic succeed in his mission by giving him the position of the mountain which will decide the fate of the war.

 

Note: Armenia is to the right of mountains below. Positions start from 0, with the mountain closest to Azerbaijan positioned as 0.

Mountains

 

Input:

The first line of input contains an integer n (1<n<1000) – the number of mountains separating the two countries. The next line contains the height of mountains  a[ i ], starting from the mountain closest to Azerbaijan , where 1< a[ i ] < 1000.

Output:

Print an integer that refers to the position of the mountain that will be selected by Armenia. In case of more than one position as your answer, print the one which is closest to Azerbaijan.

Sample Input
6
6 3 2 1 5 1
Sample Output
4
Time Limit: 1
Memory Limit: 256

code (c++):-

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,m=0,i;
    cin>>n;
    vector<int>a(n),b;
    for(auto &x:a)cin>>x;
    for(i=n-1;i>=0;i--){
        if(a[i]>m){m=a[i];b.push_back(i);}
    }
    if(b.size()%2==1){
        cout<<b[b.size()/2];
    }
    else{
        cout<<b[b.size()/2];
    }
}

Code (c):-

#include<stdio.h>
int main(){
int n, count=0;
scanf("%d", &n);
int ar[n], arr[n];
for(int i=0; i<n; i++)
scanf("%d", &ar[i]);

int k=ar[n-1];
for(int i=n-1; i>=0; i--){
if(ar[i]>k){
arr[count]=i;
count++;
k=ar[i];
}
else
continue;
}
int k1=((count+1)/2)-1, k2=(count/2)-1;
if(count%2 != 0){
printf("%d", arr[k1]);
}
else
printf("%d", arr[k2]);
return 0;
}
Recommended post:-

Hackerearth Problems:-

Data structure:-

Key points:-

Tags: