SyntaxPilot
Courses/C Coding Questions/Lesson 7
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C Coding Questions · Lesson 7 of 30

Array questions I

largest and second largest (with duplicates)min and max in one passsum and average (integer division trap)

These are the notes for C Coding Questions, episode 7, placement practice for people who finished the SyntaxPilot C course. The first array questions: the largest and second largest element (with duplicates and negative numbers), the minimum and maximum in one pass (and with fewer comparisons), and the sum and average (the integer division trap and the overflow trap).

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, Linux x86-64, 32-bit int), the SyntaxPilot compiler's C command with warnings on, and every output below is real.

Arrays in one picture: a class marks register

In a marks register In C
one row per student, numbered an array: int a[100]; is 100 ints stored side by side
go straight to row 3 a[3]: the index is the position, from 0 to n - 1
find the topper by reading every row once one pass: one for loop over the array, time O(n)
  • An array is a fixed number of values of one type, stored next to each other in memory.
  • The index of an element is its position. The first is a[0], the last of n elements is a[n - 1]. Reading a[n] or a[-1] is outside the array: undefined behaviour (UB), the C standard promises nothing about what happens.
  • One pass means looking at every element once. If the array doubles in size, the work doubles: O(n) ("big O of n") time.
  • O(1) extra space means the program needs only a few variables, however big the array is.

All three programs read the input in the same format: first n, then n integers.

Q1: Largest and second largest

Problem. Read n, then n integers. Print the largest and the second largest: the biggest value that is strictly smaller than the largest. If there is none, say so.

Input Output
5 / 12 35 1 10 34 largest 35, second 34
3 / -5 -2 -9 largest -2, second -5
4 / 10 10 5 3 largest 10, second 5 (not 10 again)
3 / 7 7 7 largest 7, no second largest
1 / 42 largest 42, no second largest

Edge cases: all negative numbers, duplicates of the largest, all equal, a single element.

Think out loud

No sorting needed. Keep two boxes, first and second, like a race with two medals:

  • a number bigger than first: the old first moves down to second, the number becomes first;
  • otherwise, a number bigger than second becomes second.

For 12 35 1 10 34: first 12 → first 35, second 12 → no change → no change → second 34.

The obvious attempt: start both at 0

#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int first = 0, second = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > first) {
            second = first;
            first = a[i];
        } else if (a[i] > second) {
            second = a[i];
        }
    }
    printf("largest %d, second %d\n", first, second);
    return 0;
}

Input 5 12 35 1 10 34:

largest 35, second 34

Input 3 -5 -2 -9:

largest 0, second 0

Input 4 10 10 5 3:

largest 10, second 10

Two wrong answers, and no warning from the compiler.

Why it failed

  1. Starting at 0. No negative number is ever bigger than 0, so 0 "wins", a value that isn't even in the list. Never start a maximum at a made-up value: start at a[0], an element that really exists.
  2. Duplicates. The second 10 is not bigger than first (10), but it is bigger than second, so it slips in. A copy of the largest is not the second largest: second may only take values strictly smaller than first.
  3. No second at all. For 7 7 7 there is no second largest. A flag found remembers whether we have seen any second value.

The fix

#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    if (n < 1 || n > 100) {
        printf("n must be 1 to 100\n");
        return 0;
    }
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int first = a[0], second = 0, found = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > first) {
            second = first;
            first = a[i];
            found = 1;
        } else if (a[i] < first && (!found || a[i] > second)) {
            second = a[i];
            found = 1;
        }
    }
    if (found) printf("largest %d, second %d\n", first, second);
    else printf("largest %d, no second largest\n", first);
    return 0;
}

Input 3 -5 -2 -9:

largest -2, second -5

Input 4 10 10 5 3:

largest 10, second 5

Input 3 7 7 7:

largest 7, no second largest

Input 1 42:

largest 42, no second largest

Input 5 12 35 1 10 34:

largest 35, second 34

Input 4 3 10 10 8:

largest 10, second 8

Input 0:

n must be 1 to 100

Complexity: one pass, O(n) time; O(1) extra space (besides the input array).

Why not sort?

Sorting first and reading from the end works, but sorting costs O(n log n) (faster than O(n²) but slower than one pass), and you still have to skip the copies of the largest. One pass with two boxes is O(n) and handles duplicates in the same loop. That is the answer interviewers want.

Q2: Min and max in one pass

Problem. Read n ≥ 1, then n integers (a week of temperatures). Print the smallest and the largest, in one pass. Interview follow-up: how many comparisons does your code make? A comparison is one check like a < b.

Input Output
6 / 4 9 -3 7 0 5 min -3, max 9
1 / -8 min -8, max -8

The obvious attempt: INT_MAX without <limits.h>

Starting min at the biggest possible int makes any number smaller, and max at the smallest. Both programs below count comparisons in cmp.

#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int min = INT_MAX, max = INT_MIN, cmp = 0;
    for (int i = 0; i < n; i++) {
        cmp++;
        if (a[i] < min) min = a[i];
        cmp++;
        if (a[i] > max) max = a[i];
    }
    printf("min %d, max %d, comparisons %d\n", min, max, cmp);
    return 0;
}

Compiler output (it does not compile):

main.c: In function 'main':
main.c:7:15: error: 'INT_MAX' undeclared (first use in this function)
    7 |     int min = INT_MAX, max = INT_MIN, cmp = 0;
      |               ^~~~~~~
main.c:2:1: note: 'INT_MAX' is defined in header '<limits.h>'; did you forget to '#include <limits.h>'?
    1 | #include <stdio.h>
  +++ |+#include <limits.h>
    2 | 
main.c:7:15: note: each undeclared identifier is reported only once for each function it appears in
    7 |     int min = INT_MAX, max = INT_MIN, cmp = 0;
      |               ^~~~~~~
main.c:7:30: error: 'INT_MIN' undeclared (first use in this function)
    7 |     int min = INT_MAX, max = INT_MIN, cmp = 0;
      |                              ^~~~~~~
main.c:7:30: note: 'INT_MIN' is defined in header '<limits.h>'; did you forget to '#include <limits.h>'?

Why: INT_MAX lives in <limits.h>

INT_MAX (2,147,483,647) and INT_MIN (-2,147,483,648) are macros: names that the preprocessor replaces with numbers before the program is compiled. They are defined in the header <limits.h>, and <stdio.h> doesn't bring them in. gcc even prints the fix in its note. (Starting min = max = a[0] also works and needs no header.)

#include <stdio.h>
#include <limits.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int min = INT_MAX, max = INT_MIN, cmp = 0;
    for (int i = 0; i < n; i++) {
        cmp++;
        if (a[i] < min) min = a[i];
        cmp++;
        if (a[i] > max) max = a[i];
    }
    printf("min %d, max %d, comparisons %d\n", min, max, cmp);
    return 0;
}

Input 6 4 9 -3 7 0 5:

min -3, max 9, comparisons 12

Input 1 -8:

min -8, max -8, comparisons 2

Input 3 -5 -2 -9:

min -9, max -2, comparisons 6

Correct, but 2 comparisons per element: 12 for 6 numbers.

The pair trick: about 3n/2 comparisons

Take the numbers two at a time:

  1. Compare the two numbers of the pair with each other (1 comparison): now you know the smaller and the bigger.
  2. The smaller can never be a new maximum, and the bigger can never be a new minimum. So compare the smaller only with min and the bigger only with max (2 comparisons).

That is 3 comparisons per 2 numbers instead of 4. If n is odd, the first element starts as both min and max; if n is even, one comparison sets them from the first pair. In total about 3n/2 − 2 comparisons (7 for n = 6) instead of 2n.

#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int min, max, i, cmp = 0;
    if (n % 2 == 1) {
        min = max = a[0];
        i = 1;
    } else {
        cmp++;
        if (a[0] < a[1]) { min = a[0]; max = a[1]; }
        else { min = a[1]; max = a[0]; }
        i = 2;
    }
    for (; i + 1 < n; i += 2) {
        int small = a[i], big = a[i + 1];
        cmp++;
        if (small > big) { small = a[i + 1]; big = a[i]; }
        cmp++;
        if (small < min) min = small;
        cmp++;
        if (big > max) max = big;
    }
    printf("min %d, max %d, comparisons %d\n", min, max, cmp);
    return 0;
}

Input 6 4 9 -3 7 0 5:

min -3, max 9, comparisons 7

Input 1 -8:

min -8, max -8, comparisons 0

Input 7 4 9 -3 7 0 5 11:

min -3, max 11, comparisons 9

Input 3 -5 -2 -9:

min -9, max -2, comparisons 3

Complexity: both versions are O(n) time and O(1) extra space. The pair trick saves about a quarter of the comparisons, not a whole loop; it matters when comparing is expensive (for example comparing long strings).

Q3: Sum and average

Problem. Read n, then n integers. Print the sum and the average with two decimal places.

Input Output
3 / 10 20 30 sum 60, average 20.00
2 / 1 2 sum 3, average 1.50
3 / three times 2000000000 sum 6000000000, average 2000000000.00
0 rejected (an average of nothing is a division by zero)

The obvious attempt

#include <stdio.h>

int main() {
    int n, a[100], sum = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) sum = sum + a[i];
    float avg = sum / n;
    printf("sum %d, average %.2f\n", sum, avg);
    return 0;
}

Input 3 10 20 30:

sum 60, average 20.00

Input 2 1 2:

sum 3, average 1.00

Why: integer division

sum and n are both int, so sum / n is integer division: 3 / 2 is 1, and the .5 is thrown away (C rounds towards zero). Only then is 1 stored in the float. The type on the left doesn't change how the right side is computed.

The fix is a cast: (double)sum converts sum to a double before the division, so the division is done in doubles. (double)(sum / n) would be too late: it casts the already-truncated result.

#include <stdio.h>

int main() {
    int n, a[100], sum = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) sum = sum + a[i];
    double avg = (double)sum / n;
    printf("sum %d, average %.2f\n", sum, avg);
    return 0;
}

Input 2 1 2:

sum 3, average 1.50

Input 3 2000000000 2000000000 2000000000:

sum 1705032704, average 568344234.67

Why: the sum overflowed

Each number fits in an int (up to 2,147,483,647), but their sum, 6,000,000,000, doesn't. Going past the limit of a signed integer is signed overflow, and in C that is undefined behaviour: the language promises nothing. This build happened to wrap around and print 1705032704 (6,000,000,000 − 4,294,967,296). The fix: keep the sum in a long long (at least 64 bits, up to about 9.2 × 10¹⁸) and print it with %lld. Also check n ≥ 1.

#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    if (n < 1 || n > 100) {
        printf("n must be 1 to 100\n");
        return 0;
    }
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    long long sum = 0;
    for (int i = 0; i < n; i++) sum = sum + a[i];
    double avg = (double)sum / n;
    printf("sum %lld, average %.2f\n", sum, avg);
    return 0;
}

Input 3 2000000000 2000000000 2000000000:

sum 6000000000, average 2000000000.00

Input 2 1 2:

sum 3, average 1.50

Input 3 -1 -2 2:

sum -1, average -0.33

Input 3 10 20 30:

sum 60, average 20.00

Input 0:

n must be 1 to 100

Complexity: one pass, O(n) time, O(1) extra space.

Complexity summary

Question Obvious attempt Fixed Time Extra space
Largest and second wrong for negatives and duplicates start at a[0], second < first, a found flag O(n) O(1)
(by sorting) O(n log n)
Min and max compile error without <limits.h> 2 comparisons per element O(n) O(1)
(pair trick) about 3n/2 comparisons O(n) O(1)
Sum and average 1.00 for 1 2; overflow for big numbers long long sum, (double)sum / n O(n) O(1)

Common mistakes (and the real messages)

Mistake What you see Why Fix
int first = 0, second = 0; no error: largest 0, second 0 for -5 -2 -9 no negative number beats 0 first = a[0]
else if (a[i] > second) no error: second 10 for 10 10 5 3 a copy of the largest slips in a[i] < first && ...
no "none" case 7 7 7 prints a made-up second there is no second largest a found flag
int min = INT_MAX; without the header error: 'INT_MAX' undeclared (first use in this function) and note: 'INT_MAX' is defined in header '<limits.h>'; did you forget to '#include <limits.h>'? it is a macro from <limits.h> #include <limits.h>
float avg = sum / n; no error: 1.00 for 1 2 int / int drops the fraction (double)sum / n
(double)(sum / n) 1.00 the cast comes after the division cast sum, not the result
int sum of big numbers no error: 1705032704 signed overflow (UB) long long sum, %lld
no check of n division by zero for n = 0 an average of nothing reject n < 1

Your turn: third largest distinct (solution)

Problem. Read n, then n integers. Print the third largest distinct value (copies count once), or "no third largest". 5 1 9 9 7 3 → 5 (the distinct values from the top are 9, 7, 5). 4 4 2 → no third largest.

Idea. Three boxes first, second, third with flags have2 and have3. Skip a value equal to one you already hold. A bigger value pushes the others down one place.

Show the solution
#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    if (n < 1 || n > 100) {
        printf("n must be 1 to 100\n");
        return 0;
    }
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int first = a[0], second = 0, third = 0, have2 = 0, have3 = 0;
    for (int i = 1; i < n; i++) {
        int x = a[i];
        if (x == first || (have2 && x == second) || (have3 && x == third)) continue;
        if (x > first) {
            third = second; have3 = have2;
            second = first; have2 = 1;
            first = x;
        } else if (!have2 || x > second) {
            third = second; have3 = have2;
            second = x; have2 = 1;
        } else if (!have3 || x > third) {
            third = x; have3 = 1;
        }
    }
    if (have3) printf("third largest %d\n", third);
    else printf("no third largest\n");
    return 0;
}

Input 6 5 1 9 9 7 3:

third largest 5

Input 3 4 4 2:

no third largest

Input 5 -1 -2 -3 -4 -5:

third largest -3

Input 4 10 9 9 8:

third largest 8

Input 6 3 3 2 2 1 1:

third largest 1

Input 1 5:

no third largest

Time O(n), extra space O(1).

Practice questions (with solutions)

1. Second smallest element. The mirror image of Q1.

Solution
#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    if (n < 1 || n > 100) {
        printf("n must be 1 to 100\n");
        return 0;
    }
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int first = a[0], second = 0, found = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] < first) {
            second = first;
            first = a[i];
            found = 1;
        } else if (a[i] > first && (!found || a[i] < second)) {
            second = a[i];
            found = 1;
        }
    }
    if (found) printf("smallest %d, second smallest %d\n", first, second);
    else printf("smallest %d, no second smallest\n", first);
    return 0;
}

Input 5 12 35 1 10 34:

smallest 1, second smallest 10

Input 4 1 1 2 3:

smallest 1, second smallest 2

Input 3 7 7 7:

smallest 7, no second smallest

2. Count the elements greater than the average. Compare a[i] * n > sum in long long, so no division (and no rounding) is needed.

Solution
#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    if (n < 1 || n > 100) {
        printf("n must be 1 to 100\n");
        return 0;
    }
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        sum = sum + a[i];
    }
    int count = 0;
    for (int i = 0; i < n; i++)
        if ((long long)a[i] * n > sum) count++;
    printf("average %.2f, %d above it\n", (double)sum / n, count);
    return 0;
}

Input 5 10 20 30 40 50:

average 30.00, 2 above it

Input 3 5 5 5:

average 5.00, 0 above it

Input 4 1 2 2 2:

average 1.75, 3 above it

3. Index of the largest element (the first one if there is a tie). Keep the index, not the value; > (not >=) keeps the first of equal values.

Solution
#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    if (n < 1 || n > 100) {
        printf("n must be 1 to 100\n");
        return 0;
    }
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int best = 0;
    for (int i = 1; i < n; i++)
        if (a[i] > a[best]) best = i;
    printf("largest %d at index %d\n", a[best], best);
    return 0;
}

Input 5 3 9 2 9 1:

largest 9 at index 1

Input 3 -5 -2 -9:

largest -2 at index 1

Quick quiz

int a = 7, b = 2;
printf("%d %.1f %.1f\n",
       a / b, a / 2.0, (double)(a / b));

(A) 3 3.5 3.0 (B) 3 3.5 3.5 (C) 3.5 3.5 3.5 (D) 3 3.0 3.0

Answer

(A). 7 / 2 is integer division: 3. 7 / 2.0 has a double operand, so the division is done in doubles: 3.5. (double)(a / b) divides first (3) and casts too late: 3.0.

Output:

3 3.5 3.0

Interview questions

  1. Find the second largest element in one pass. Two variables, start from a[0]; a bigger value pushes first down to second; a value smaller than first but bigger than second replaces second. O(n), O(1).
  2. Why not sort to find the second largest? Sorting is O(n log n) and still needs to skip duplicates; one pass is O(n).
  3. What should the second largest of 10 10 5 be? 5: the second largest distinct value. Ask the interviewer if unsure, and handle "no second largest".
  4. How many comparisons do you need for min and max? About 3n/2 − 2 with the pair method, instead of 2n − 2.
  5. Why does float avg = sum / n; give the wrong answer? Both operands are int, so the division is integer division before the value is stored.
  6. Where are INT_MAX and INT_MIN defined? In <limits.h>.
  7. How do you avoid overflow when summing many ints? Accumulate in a long long (or check before adding).
  8. What is undefined behaviour? Code whose result the C standard doesn't define, such as signed overflow or reading outside an array. The program may print anything, crash, or seem to work.

Glossary

Term Meaning Example
Array A fixed number of values of one type, stored side by side int a[100];
Element One value in an array a[3]
Index The position of an element, from 0 to n − 1 a[0] is the first
One pass Looking at every element exactly once one for loop
Big O notation How the work grows with the input size O(n), O(n log n)
O(n) time Double the input, double the work one pass
O(1) extra space A fixed number of extra variables first, second
Second largest The biggest value strictly smaller than the largest 10 10 5 → 5
Distinct Counting copies once 9 9 7 has 2 distinct values
Flag A variable that remembers whether something happened found = 1
Comparison One check like a < b cmp++ counts them
Pair trick Compare two elements first, then the smaller with min and the bigger with max 3 comparisons per 2 numbers
Macro A name the preprocessor replaces before compiling INT_MAX
Header A file of declarations and macros you #include <limits.h>, <stdio.h>
INT_MAX / INT_MIN The largest and smallest int 2147483647 / -2147483648
Integer division int / int: the fraction is dropped 7 / 2 = 3
Cast Converting a value to another type (double)sum
double A floating-point number with about 15-16 significant digits 1.5
long long An integer of at least 64 bits up to about 9.2 × 10¹⁸
Signed overflow A signed result too big for its type: undefined behaviour int sum of 3 × 2,000,000,000
Undefined behaviour (UB) The C standard doesn't define what happens overflow, a[n]
Edge case An input at the boundary n = 1, all equal, all negative
Sorting Putting elements in order O(n log n) with a good algorithm

Summary

  • Start a maximum or minimum at a real element, a[0], never at 0.
  • Second largest: one pass with two boxes; second only takes values smaller than first; a flag for "no second largest".
  • INT_MAX and INT_MIN need #include <limits.h>.
  • Min and max: O(n) either way; the pair trick needs about 3n/2 comparisons instead of 2n.
  • Average: cast before dividing, (double)sum / n; keep big sums in a long long and print with %lld; reject n < 1.

Next episode: Array questions II: reverse an array in place, left rotate by one, and rotate by k with the reversal trick (k larger than n).