Skip to content
GATEiit

GATE CSE 2021 Set 1 Q12: Comparisons needed to find both minimum and maximum

Question

Let P be an array containing nn integers. Let tt be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of nn elements. Which one of the following choices is correct?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2021 final answer key)

Concept used: Processing elements in pairs finds min and max with about ⌈3n/2⌉−2\lceil 3n/2 \rceil - 2 comparisons, which is optimal.

First step: Compare each pair first, then the smaller with the current min and the larger with the current max: 3 comparisons per 2 elements.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2021 Set 1 questions →