Pushpa PUSH7PA Solution Codechef

by

Table of Contents

Pushpa PUSH7PA Solution Codechef

Pushpa has entered Chefland and wants to establish Pushpa-Raj here too.

Chefland has N towers where the height of the ith tower is Hi. To establish Pushpa-Raj, Pushpa does the following:

Initially, Pushpa chooses any tower i (1≤i≤N) and lands on the roof of that tower.
Let X denote the height of the tower Pushpa is currently on, then, Pushpa can land on the roof of any tower j (1≤j≤N) such that the height of the jth tower is (X+1).
Let i denote the index of the tower on which Pushpa lands, then, the height of all towers except tower i increases by 1 after each jump including the initial jump.

To establish Pushpa-Raj, Pushpa wants to land at the maximum height possible. Determine the maximum height Pushpa can reach.

Input Format
The first line contains a single integer T – the number of test cases. Then the test cases follow.
The first line of each test case contains an integer N – the number of towers
The second line of each test case contains N space-separated integers H1,H2,…,HN denoting the initial heights of each of the towers from the ground.

Output Format
For each test case, output in a single line the maximum height achieved by Pushpa.

Constraints

  • 1≤T≤10
  • 1≤N≤105
  • 1≤Hi≤109

Sample Input 1
2
4
1 2 1 3
1
2

Sample Output 1
3
2

Explanation

Test case 1: If Pushpa chooses to start from tower at index 1 with height of 1 unit, then, the new heights will be [1,3,2,4]. He can then jump to the 3rd tower (with height 2 units). The updated heights of the towers is [2,4,2,5]. Pushpa is unable to make any more jumps.
The optimal way to in this case is to take an initial jump at tower 4 with height 3. The maximum height Pushpa can reach is 3.

Test case 2: There is only 1 tower so Pushpa reaches the maximum height of 2 units.

SOLUTION

Program: Pushpa PUSH7PA Solution Codechef in Python

def mf(List):
    return max(set(List), key=List.count)
t = int(input())
for i in range(0, t):
    n = int(input())
    a = list(map(int, input().split()))
    x = mf(a) + a.count(mf(a))-1
    y = max(a) + a.count(max(a)) - 1
    if x > y:
        print(x)
    else:
        print(y)

Program: Pushpa PUSH7PA Solution Codechef in C++

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--){
       int n;
       cin>>n;
 
       int h[n];
       for(int i=0;i<n;i++) cin>>h[i];
       sort(h,h+n); 
       int ans = h[n-1];
       int y=0;
       for(int i=0;i<n-1;i++){
           if(h[i]==h[i+1]){
               y++;
           }
           if(h[i]!=h[i+1] or i==n-2){
               ans = max(ans,h[i]+y);
               y=0;
           }
       }
       cout<<ans<<endl;
    }
    return 0;
}

Program: Pushpa PUSH7PA Solution Codechef in Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
         Scanner sc=new Scanner(System.in);
         int t=sc.nextInt();
         while(t-->0)
         {
             int n=sc.nextInt();
             int arr[]=new int[n];
             for(int i=0;i<n;i++)
             {                     
                  arr[i]=sc.nextInt();
             }    
             Arrays.sort(arr);
             if(n==1)
             {
                System.out.println(arr[0]);
             }
             else
            {
                int max=0;
                int c=0;
            for (int i=n-1;i>=1;i--)
                {
                    if(arr[i]==arr[i-1])
                    {
                        c++;
                    }
                    else{
                        if(max<arr[i]+c)
                        {
                        max=arr[i]+c;
                        }
                        c=0;
                    }
                }
                System.out.println(max);
            }
        }
    }
}

Related:

Leave a Comment

18 + 9 =