Average of Two Largest Numbers Without Sorting in C

This program reads N integers and finds the two largest values without sorting the array, then computes their average. The key technique: maintain two variables — first (the largest seen so far) and second (the second-largest). Scan each new element and update these two variables in one pass. Time complexity: O(n). Space: O(1) — no extra array needed.

The original post was restricted to exactly 4 numbers and used conio.h, void main(), and if-else comparisons written out for fixed indices (a[0] vs a[1] vs a[2] vs a[3] — each hardcoded). This rewrite works for any N ≥ 2 with a clean one-pass scan.

C Program: Average of Two Largest Numbers (Without Sorting)

/* Average of the two largest numbers in an array (without sorting)
 * Compile: gcc -ansi -Wall -Wextra largest_two.c -o largest_two */
#include <stdio.h>

#define MAX 100

int main(void)
{
    int a[MAX], n, i;
    int first, second;  /* first = largest, second = second-largest */

    printf("Enter number of elements (min 2, max %d): ", MAX);
    if (scanf("%d", &n) != 1 || n < 2 || n > MAX) {
        printf("Invalid count.\n");
        return 1;
    }

    printf("Enter %d integers:\n", n);
    for (i = 0; i < n; i++)
        if (scanf("%d", &a[i]) != 1) { printf("Invalid.\n"); return 1; }

    /* Initialize first and second from first two elements */
    if (a[0] >= a[1]) {
        first = a[0];
        second = a[1];
    } else {
        first = a[1];
        second = a[0];
    }

    /* Scan remaining elements */
    for (i = 2; i < n; i++) {
        if (a[i] > first) {
            second = first;  /* old first becomes second */
            first = a[i];    /* new element becomes first */
        } else if (a[i] > second) {
            second = a[i];   /* new second, first unchanged */
        }
    }

    printf("\nArray      : ");
    for (i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\nLargest    : %d\n", first);
    printf("2nd Largest: %d\n", second);
    printf("Average of two largest: %.2f\n", (double)(first + second) / 2.0);

    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra largest_two.c -o largest_two
./largest_two

Sample Output

Enter number of elements (min 2, max 100): 5
Enter 5 integers:
3 9 2 7 5

Array      : 3 9 2 7 5
Largest    : 9
2nd Largest: 7
Average of two largest: 8.00

Step-by-Step Trace — [3, 9, 2, 7, 5]

Step	a[i]	first	second	Reason
Init from [0],[1]	—	3	—	a[0]=3, a[1]=9: a[1]>a[0] → first=9, second=3
Init	—	9	3
i=2	2	9	3	2 < 9 and 2 < 3 → no change
i=3	7	9	7	7 < 9 but 7 > 3 → second = 7
i=4	5	9	7	5 < 9 and 5 < 7 → no change
Result	—	9	7	Average = (9+7)/2 = 8.00

Code Explanation

Initialization from first two elements — the loop starts at i=2. Before that, we must initialize first and second from a[0] and a[1] (whichever is larger goes to first). This avoids the need to initialize first and second to INT_MIN (which would require <limits.h>) and handles all-negative arrays correctly.
The two-variable update rule — when a new element exceeds first: old first becomes the new second, new element becomes the new first. When a new element is between first and second: it becomes the new second. Otherwise: skip (smaller than both). This correctly handles the case where the new element would be the largest seen so far — it demotes the previous largest to second place.
Duplicate values — if the two largest are equal (e.g., [4, 4, 1]), first=4 and second=4, average=4.00. The algorithm handles this correctly: after the init step, if a[0]==a[1], first and second are both set to that value.
Why not sort? — sorting takes O(n log n) time and O(1)–O(n) extra space (depending on algorithm). Finding just the top 2 requires only O(n) time and O(1) extra space. For finding top-K where K is much smaller than n, this pattern generalizes to maintaining a K-element min-heap, still faster than full sorting.
Integer overflow in the average — (double)(first + second) / 2.0: the cast to double before dividing avoids integer division truncation. For very large integers, first + second could overflow int — a safer form is (double)first/2.0 + (double)second/2.0.

What This Program Teaches

The “top-K” pattern — maintaining a running maximum (or top-K) in one pass is fundamental to streaming algorithms. You cannot always store the full dataset; instead you track just what you need. A single pass with O(1) space beats sorting when you only need the extremes.
Initialize from data, not from INT_MIN — initializing first and second from a[0] and a[1] is cleaner than using INT_MIN from <limits.h>, and works correctly for all-negative arrays. Many beginners hardcode 0 as the starting maximum, which breaks when all values are negative.
Integer division vs floating-point average — in C, (7 + 9) / 2 is integer division = 8, which happens to be correct here. But (7 + 8) / 2 would give 7 (truncated), not 7.5. Always cast to double before dividing when the result might not be a whole number.

Related Programs

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.

C Program to find the average of largest two of the given numbers in the array.