GATE 2024 CS1 Q.43: solution and answer

Official answer: ASource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

1. Min-heap property: for any parent–child pair, key(parent) ≤ key(child). If a node has at least one child, that child's key is ≥ the node's key, and since all 105 elements are distinct, the child's key must be strictly greater. So a node with a child can never hold the maximum element.

2. Therefore the maximum element must sit at a node with no children — a leaf of the heap.

3. Using 1-indexed array representation for $n=105$ nodes, node $i$ has a child at $2i$, which exists only when $2i\le n$, i.e. $i\le \lfloor n/2\rfloor =\lfloor 105/2\rfloor =52$. So indices $1$ through $52$ are internal (non-leaf) nodes.

4. Hence leaf indices run from $53$ to $105$, giving $105-53+1=53$ leaf positions.

5. For each of these 53 leaf positions, a valid min-heap can be constructed with the maximum element placed at that leaf: put the largest value there and arrange the remaining 104 values anywhere else consistent with the min-heap order (always possible, since a leaf imposes no downward constraint and its parent only needs to be $\le$ the maximum value, which trivially holds). So every leaf index is achievable.

6. Therefore the number of possible values of $k$ equals the number of leaf positions $=53$, which is option (A).