Question Name:Chandu and his Girlfriend

#include<iostream>
 
using namespace std;
 
void merge(int start,int mid,int end,int a[])
{
    int arr[end-start+1],p=start,q=mid+1,k=0,i;
    
    for(i=start;i<=end;i++)
    {
        if( p > mid)
        {
            arr[k++]=a[q++];
        }
        else if ( q > end)
        {
            arr[k++]=a[p++];
        }
        else if(a[p]>a[q])
        {
            arr[k++]=a[p++];
        }
        else
        {
            arr[k++]=a[q++];
        }
    }
    
    for(i=start;i<=end;i++)
    {
        a[i]=arr[i-start];
    }
}
 
void mergesort(int start,int end,int a[])
{
    if(start<end)
    {
        int mid=(start+end)/2;
        mergesort(start,mid,a);
        mergesort(mid+1,end,a);
        
        merge(start,mid,end,a);
    }
}
int main()
{
    int t,l;
    cin >> t;
    
    for(l=0;l<t;l++)
    {
        int n;
        cin >> n;
        
        int a[n],i;
        
        for(i=0;i<n;i++)
        {
            cin >> a[i];
        }
        
        int start=0,end=n-1;
        
        mergesort(start,end,a);
        
        for(i=0;i<n;i++)
        {
            cout << a[i] << " ";
        }
        
        cout << endl;
    }


	return 0;
}

Problem Description

Chandu’s girlfriend loves arrays that are sorted in non-increasing order. Today is her birthday. Chandu wants to give her some sorted arrays on her birthday. But the shop has only unsorted arrays. So, Chandu bought T unsorted arrays and is trying to sort them.

But, he doesn’t have much time to sort the arrays manually as he is getting late for the birthday party. So, he asked you to write a program to sort the T arrays in non-increasing order. Help him, or his girlfriend will kill him.

Input:
First line contains an integer T, denoting the number of test cases.
First line of each test case contains an integer N, denoting the size of the array.
Second line contains N space separated integers, denoting the array elements Ai.

Output:
For each test case, print the sorted array in non-increasing order.

Constraints:
1 <= T <= 100
1 <= N <= 10^5
0 <= Ai <= 10^9

  • Test Case 1

    Input (stdin)

    2
    4
    4 3 5 1
    3
    3 1 2

    Expected Output

    5 4 3 1
    3 2 1

  • Test Case 2

    Input (stdin)

    2
    5
    2 5 2 4 3
    5
    5 4 2 3 1

    Expected Output

    5 4 3 2 2
    5 4 3 2 1

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.