Recent CP News

Game of Infinity || Dedicated level of Infinity

A simple question again about Game of Infinity!

These are the people from normal and who have shown utmost dedication towards Competitive Programming..!

You will be provided with the name of the coder and no. of hours he/she spent on coding.

You need to output top 3 names of the coders who spent the most time in coding.

Note: Time (no. of hours) given for all coders will be unique. More technically, no two coders will have the same amount of time.

See the sample case for better understanding.

Input format:

The first line consists of a total number of coders, let’s say ‘n’.

Each of the next n lines consists of a string, let’s say ‘N’ (name of a coder) and a number let’s say, ‘T’ (time).

Output format:

Output names of top 3 coders that spent maximum time in coding.

Constraints:

3 <= n <= 100

1 <= |N| <= 10

1 <= T <= 1000

SAMPLE INPUT

7
Darshan 78
Harshad 90
Jaimin 87
Nirav 88
Hardik 1
Fenil 70
Lovlin 5

SAMPLE OUTPUT 

Harshad
Nirav
Jaimin

 Explanation

Harshad spent 90 hours in coding, which is maximum, so his name is at first.

After Harshad, Nirav spent 88 hours in coding, which is maximum, so his name is second.

After Nirav, Jaimin spent 87 hours in coding, which is maximum, so his name comes third.

SOLUTION DESCRIPTION

A simple approach here to get the top 3 coder-names as per the maximum time they gave is just store their names in a String array having an index as time. Then, just iterate from last till we don’t get top 3 coder names and then break.

Time Complexity for this approach: O(1000)

One other approach is to sort the names in decreasing order as per time was taken and then print first 3 among them.

Time Complexity for this approach: (nlogn)

The first approach is followed here.

import java.util.*;
import java.math.*;

public class Sol {
    public static void main(String args[]) throws Exception {
        Scanner in = new Scanner(System.in);

        int no_of_coders = in.nextInt();

        // now make and array to store names of coders for different time
        // Size of an array will be the maximum limit of time of all coders
        // Check constraint, max limit for time for all coders is 1000.
        // So we can make any array of size greater than 1000.

        String names_of_coders[] = new String[1005];

        for(int i=0;i<no_of_coders;i++) {
            String name = in.next();
            int time = in.nextInt();        // treat time as index to store name

            names_of_coders[time] = name;
        }

        int top = 0;
        int index = 1000;           // start searching from last possible time

        // since we have to collect top 3 names so till top is not 3, we have to loop
        while(top != 3) {
            // check if there is a coder at this index (time).
            // If yes, then we have to print the name as this coder will be in top 3.
            // If yes, don't forget to increment top variable (as we included this coder)
            // If no, then do nothing..!

            if(names_of_coders[index] != null) {        // to check if there is a coder
                System.out.println(names_of_coders[index]);
                top++;
            }

            index--;        // decrease the time (index)
        }
    }
}

{Code With Code@ter}

Give Your Reviews




Leave a Reply