GATE CSE 2005 | Question: 5

Question

A program $P$ reads in $500$ integers in the range $[0, 100]$ representing the scores of $500$ students. It then prints the frequency of each score above $50$. What would be the best way for $P$ to store the frequencies?

• A. An array of $50$ numbers

• B. An array of $100$ numbers

• C. An array of $500$ numbers

• D. A dynamically allocated array of $550$ numbers

Comments

it will be like an array A[50].

A[0] represents how many students got 51 marks("It then prints the frequency of each score above 50"), A[1] represents how many students got 52 marks(since 52>50) and so on.

---

@ HeadShot
A small correction here 

"So the worst case would be -> allocate every student marks > 50 then the max size of array needed is "50" because by pigeon hole principle, after 100, elements will be repeated."
 

---

@ prithatiti Elements can start repeating after 1 element also. You should say after 100 elements, elements will start repeating for sure according to the pigeon hole principle.

Answer 1

As we our area of interest is only the $50$ numbers so take An array of $50$ numbers where $A[0]$ corresponds to $51...A[49]$ corresponds to $100$ then after reading an input just increment the counter in correct position as said above.

Correct Answer: $A$

Comments

@VINAY769
Yes, you are absolutely right. As the program has printed only the frequency score above 50 that means no student has got the marks less than or equal to 50.

---

You can do all the count and array of frequency of each number in one go only or O(n) time no need to count for 51 , 52 and …. so on seperately , time complexity is then became O($n^2$).

---

if you thought; B) was the answer

that is make a arr[100] and then increment arr[marks] += 1 and in this way you could store frequency of marks of each student,

range of marks is [0,100] i.e 101 possible mark values so you won't be able to count all frequencies anyways (as arr can only store 0~99 mark value in this was) and nor do we wish to store all frequency option A) is enough 

Answer 2

Let read () be a function which returns the current value read from given  500 integers.

P[50] array of 50 elements ,where all elements is initialized to 0.

Program P()
{
For(i=1 to 500)
{
   x = read();
     if(x>50)
   {
     P[x%50]++; // here we can use P[x] ++ but  for that we would require array of size 100
   }
}
}

Therefore answer is A

Comments

here we can use P[x] ++ but  for that we would require array of size 100

why size 100 only? 

---

The question seems to be related to counting sort, also in counting sort we create a temp array to store the frequencies of the numbers encountered.

In that we create the array in the range of 0 to k but here the question asks to find only numbers above 50 so require array of size 50.

Answer 3

Answer option (A) 

create an array of 50 elements where 0,1,2 index correspond to score 50,51,52 and so on  

see the below program 

Answer 4

Given that

Program P reads in 500 integers in the range [0,100] representing the scores of 500 students.

then prints the frequency of each score above 50.It means frequency of scores 51 to 100(because score range is given [0,100]).

Here to store frequency of scores 51 to 100 (50 scores) we can use array of size 50.

we can use array of size 50 with starting index 51 to last index 100 and we can store frequency of each score 51 to 100. Here in array 51 to 100 represents indexes and corresponding values represent frequency of each score.

[example: a[51...100]

a[51]=7(assume 51 frequency is 7)

a[52]=8(assume 52 frequency is 8)

….

…..

…..

a[100]=20(assume 100 frequency is 20)   ]

 

Correct Answer : A

Answer 5