Last Updated on March 25, 2022 by Ria Pathak
Concepts Used
Sorting
Difficulty Level
Easy
Problem Statement (Simplified):
Print the last number left in the array after deleting the largest number in the array then the smallest number repeatedly.
See original problem statement here
Test Case
Input:
1
3
2 1 3
Output:
2
Explanation:
Teacher 1 wants to minimize the mark, so we remove the largest mark i.e. 3.
Teacher 2 wants to maximize the mark, so we remove the smallest mark i.e. 1.
Now, there is only 2 left, so we print 2 as our answer.Solving Approach :
Bruteforce Approach:
1) We can find the largest and smallest element and remove them from array serial wise until the last element is left in the array.
2) This would take O(
N!) in the worst time as we decrease array size by 2 in every iteration, and again iterate on the array. But this is not a very efficient approach, we can use sorting, to solve this problem more efficiently.
Efficient Approach:
Observation: We can see that size of array goes from 1 to 106, in worse conditions let the size of the array be 10^6 if we sort this array using any of sorting techniques i.e. Bubble Sort, Insertion Sort, Selection sort. They all take O(N2) in worst cases, which results in 1012 iterations when the size of the array is 106. So we, can’t choose the above three sorting algorithms. We use Merge Sort to sort array as it sorts array in linearithmic time complexity (n * log(n)).
1) We sort the array, and can see the largest number in the array is at its very end, and the first number is the smallest number of the array.
2) So if we remove both of them, our array becomes shorter by 2 elements and starts from
1stindex and ends at(last index - 1)thindex.3) Now two cases rises:
- Case-1: If the array is Odd in size, and we remove elements from both sides repeatedly, the last element left would be the middle element, so we print the middle element directly.
- Case-2: If the array is Odd in size, and we remove elements from both sides repeatedly, the last element left would be the last smaller element. As we have to remove the largest element first, the last element left would be the last smaller element, which would be (size / 2)th element in the array. So we print the
(size / 2)thelement.
NOTE: We directly print the element, no iteration required.
Example
Solutions
#include <stdio.h>
void merge(int arr[], int start, int mid, int end){
int left[mid-start+1];
int right[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
int main()
{
int test;
scanf("%d",&test);
while(test--){
int n;
scanf("%d",&n);
int marks[n];
for(int i=0; i<n; i++)
scanf("%d",&marks[i]);
mergeSort(marks,0,n-1);
if(n%2==0)
printf("%d\n",marks[(n/2)-1]);
else
printf("%d\n",marks[(n/2)]);
}
}
#include <bits/stdc++.h>
using namespace std;
void merge(int arr[], int start, int mid, int end){
int left[mid-start+1]={0};
int right[end-mid]={0};
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
int main()
{
int test;
cin>>test;
while(test--){
int n;
cin>>n;
int marks[n];
for(int i=0; i<n; i++)
cin>>marks[i];
mergeSort(marks,0,n-1);
if(n%2==0)
cout<<marks[(n/2)-1]<<endl;
else
cout<<marks[(n/2)]<<endl;
}
}
import java.util.*;
import java.io.*;
public class Main {
static void merge(int arr[], int start, int mid, int end){
int left[] = new int[mid-start+1];
int right[] = new int[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
static void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
while(test-->0){
int n = sc.nextInt();
int marks[] = new int[n];
for(int i=0; i<n; i++)
marks[i] = sc.nextInt();
mergeSort(marks,0,n-1);
if(n%2==0)
System.out.println(marks[(n/2)-1]);
else
System.out.println(marks[(n/2)]);
}
}
}
def merge(arr, start, mid, end): left = [0 for i in range(mid - start + 1)] right = [0 for i in range(end - mid)] for i in range(start, mid + 1): left[i - start] = arr[i] for i in range(mid + 1, end + 1): right[i - (mid + 1)] = arr[i] leftIndex = 0 rightIndex = 0 arrIndex = start while leftIndex <= mid - start and rightIndex < end - mid: if(left[leftIndex] < right[rightIndex]): arr[arrIndex] = left[leftIndex] leftIndex += 1 else: arr[arrIndex] = right[rightIndex] rightIndex += 1 arrIndex += 1 while(leftIndex <= mid - start): arr[arrIndex] = left[leftIndex] leftIndex += 1 arrIndex += 1 while(rightIndex < end - mid): arr[arrIndex] = right[rightIndex] rightIndex += 1 arrIndex += 1 def mergeSort(arr, start, end): if(end == start): return mergeSort(arr, start, (start + end) // 2) mergeSort(arr, ((start + end) // 2) + 1, end) merge(arr, start, (start + end) // 2, end) for _ in range(int(input())): n = int(input()) marks = list(map(int, input().split())) mergeSort(marks, 0, n - 1) if n % 2 == 0: print(marks[(n//2) - 1]) else: print(marks[(n//2)])
[forminator_quiz id="1345"]
where n is the size of array.
Space Complexity : O(1)
This article tried to discuss Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.