GATE CSE 2025 | Set 2 | Question: 10

Question

​​​​Consider an unordered list of $N$ distinct integers.

What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

• A. $1$
• B. $N-1$
• C. $N$
• D. $2N-1$

 

Comments

Hmmm , yes works !

---

 similar question 2015

---

 

Here is the breakdown for both scenarios, assuming the list has $N \ge 2$ elements:

1. If the integers are DISTINCT: 1 comparison

You only need exactly 1 comparison.

Why: Take any two random elements from the list and compare them. Because all elements in the list are distinct, they cannot be equal. One will definitively be smaller than the other. The smaller of those two elements is guaranteed not to be the largest element in the entire list.

 

2. If the integers are NOT DISTINCT: $N-1$ comparisons

In the worst-case scenario, you will need $N-1$ comparisons.

Why: If the list can contain duplicates, comparing two elements might reveal that they are equal (e.g., comparing 10 and 10). If they are equal, you learn nothing about whether they are the maximum value or not.

 

Answer 1

Pick any two numbers from a set of distinct numbers, one of them must be smaller than the other. The smaller of the two is guaranteed not to be the largest in the entire list. One comparison is enough find an element that is not the largest.

Answer 2

Consider any array  and variable largest

23

43

13

11

 

largest 

23

---

 Variable largest be updated with currently seen maximum value  i.e.., we consider  first element of the array as the largest .Then here comes 2 cases :

• while we see second element of the array ,if it is greater than first element then we update largest variable with second element of the array. ---> Means we have seen element which is not largest i.e.., first Element  --->Requires One Comparison

  ---

   

• If  second element of the array is lesser than first element then we don't update largest variable.--> Means  we  have  seen  element   which  is  not  largest   i.e..,  Second Element   ---> Requires One Comparison

Hence Minimum no.of Comparisons required =1 to find the element which is not largest

 

 

Comments

Great answer

Answer 3

Since all elements are distinct, there is a unique largest element. The task is to identify any one element that is not the maximum, using the fewest comparisons in the worst case.

Select any two distinct elements from the list, say $a$ and $b$. Perform a single comparison:

• If $a < b$, then $a$ cannot be the largest.
• If $b < a$, then $b$ cannot be the largest.

In either case, the smaller of the two is guaranteed not to be the maximum. Thus, one comparison suffices to produce a valid answer.

No algorithm can do better than one comparison (since without any comparison, we have no information about relative order), and no additional comparisons are necessary.

Hence, the minimum number of comparisons required is 1.

Final Answer:  
$$
\boxed{\text{A. }1}
$$

Comments

good

Answer 4

In any list, by comparing L[0] with L[1] we get an element which is the largest and another which is not the largest. So it takes only one comparision.

Answer 5

Answer is OPTION A.

Consider a basic example of an array. We need to find the element that is not maximum. SO check the first two elements of the array (length of array >= 2).

Out of these two elements, it is guarenteed that one element is not the maximum, as all the elements are distinct.

Hence we need 1 comparison between first and second element.

Answer 6

Similar Question was asked in 2015

https://gateoverflow.in/8113/gate-cse-2015-set-2-question-22