SyntaxPilot
Courses/C Coding Questions/Lesson 10
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 10 of 30

Array questions IV

two-sum (brute force vs sort + two pointers)count pairs with a given summove all zeros to the end keeping order

These are the notes for C Coding Questions, episode 10, placement practice for people who finished the SyntaxPilot C course. Array questions, part four: two sum (brute force, then sorting with qsort and two pointers), counting pairs with a given sum (with repeated values, and why the count needs long long), and moving all zeros to the end while keeping the order (and the if (a[i] = 0) typo that -Wall catches).

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. The compiler stops a program after 8 seconds (Time Limit Exceeded), like an online judge.

One picture for all three: a 500 rupee gift voucher

At the shop In C
buy two items that cost exactly 500 together (no change is given) two sum: find a[i] + a[j] == target with i != j
how many different pairs of items cost exactly 500? prices can repeat count pairs with a given sum, every pair i < j once
push the empty slots of a shelf to the back, products keep their order move zeros to the end, keep the order of the rest

Q1: Two sum

Problem. Read n and a target t, then n prices (each up to a million in size, so any sum of two fits an int). Print two prices from two different items that add up to t, or no pair.

Input Output
4 7 / 4 1 6 3 a pair adding to 7 (4 + 3, or 1 + 6)
4 8 / 4 1 6 3 no pair (8 = 4 + 4, but there is only one 4)
5 0 / -5 2 9 5 -1 -5 + 5 = 0
1 10 / 10 no pair

Edge cases: half the target appears only once, no pair, n = 1, a very big n.

The obvious attempt: try every pair (brute force)

Brute force means trying every possibility. Here: every i, every j.

#include <stdio.h>

int main() {
    int n, t, a[100];
    scanf("%d %d", &n, &t);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i] + a[j] == t) {
                printf("%d + %d = %d\n", a[i], a[j], t);
                return 0;
            }
        }
    }
    printf("no pair\n");
    return 0;
}

Input 4 7 / 4 1 6 3:

4 + 3 = 7

Input 4 8 / 4 1 6 3:

4 + 4 = 8

Why: j can be equal to i

When i = 0 and j = 0, the program adds a[0] to itself: 4 + 4 = 8, with only one 4. Start j at i + 1: then every pair is checked exactly once, with i < j. That is n(n - 1)/2 pairs, O(n²).

#include <stdio.h>

int main() {
    int n, t, a[100];
    scanf("%d %d", &n, &t);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] + a[j] == t) {
                printf("%d + %d = %d\n", a[i], a[j], t);
                return 0;
            }
        }
    }
    printf("no pair\n");
    return 0;
}

Input 4 8 / 4 1 6 3:

no pair

Input 4 7 / 4 1 6 3:

4 + 3 = 7

Stress test: 300,000 prices

A stress test is a huge input, here made by the program itself: the prices 0, 2, 4, … (all even) and an odd target, so no pair exists and every pair is checked.

#include <stdio.h>

int a[300000];

int main() {
    int n, t;
    scanf("%d %d", &n, &t);
    for (int i = 0; i < n; i++) a[i] = 2 * i;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] + a[j] == t) {
                printf("%d + %d = %d\n", a[i], a[j], t);
                return 0;
            }
        }
    }
    printf("no pair\n");
    return 0;
}

Input 300000 7:

Time Limit Exceeded (stopped after 8 seconds)

300,000 items make about 45 billion pairs (300,000 × 299,999 / 2).

The fix: sort, then two pointers from both ends

  1. Sort the prices, smallest first.
  2. l = 0 points at the cheapest item, r = n - 1 at the costliest. (A pointer here is just an index we move.)
  3. sum = a[l] + a[r]: - sum == t: found. - sum < t: we need more, so l++ (a costlier cheap item). - sum > t: too much, so r-- (drop the costliest).
  4. Stop when l meets r: no pair.

Why it is safe. If a[l] + a[r] < t, then a[l] plus any other item is even smaller (all others are ≤ a[r]), so a[l] can't be part of an answer and we drop it. The same argument drops a[r] when the sum is too big. Every step drops one item for good, so there are at most n steps. Because l < r always, an item is never added to itself.

sorted 1 3 4 6, target 7:  l=0 r=3: 1 + 6 = 7  -> found
sorted 1 3 4 6, target 8:  1 + 6 = 7 < 8 -> l++
                           3 + 6 = 9 > 8 -> r--
                           3 + 4 = 7 < 8 -> l++   l == r -> no pair

Sorting in C: qsort and a comparator

qsort from <stdlib.h> sorts any array in place:

qsort(a, n, sizeof(int), cmp);

It takes the array, the number of elements, the size of one element, and a comparator: a function we write that gets pointers to two elements and returns a negative number if the first should come first, 0 if they are equal, and a positive number if the second should come first. The pointers are const void * (a pointer to "any type"), so we turn them back into int pointers:

int cmp(const void *p, const void *q) {
    int x = *(const int *)p, y = *(const int *)q;
    return (x > y) - (x < y);   // 1, 0 or -1
}

Don't write return x - y;: for values far apart (for example INT_MIN and 1) the subtraction overflows. Episode 14 shows that bug for real. qsort takes O(n log n) time on average.

The two-pointer solution

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q) {
    int x = *(const int *)p, y = *(const int *)q;
    return (x > y) - (x < y);
}

int main() {
    int n, t, a[100];
    scanf("%d %d", &n, &t);
    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]);
    qsort(a, n, sizeof(int), cmp);
    int l = 0, r = n - 1;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == t) {
            printf("%d + %d = %d\n", a[l], a[r], t);
            return 0;
        }
        if (s < t) l++;
        else r--;
    }
    printf("no pair\n");
    return 0;
}

Input 4 7 / 4 1 6 3:

1 + 6 = 7

Input 4 8 / 4 1 6 3:

no pair

Input 5 0 / -5 2 9 5 -1:

-5 + 5 = 0

Input 1 10 / 10:

no pair

It prints 1 + 6 instead of the brute force's 4 + 3: both are correct, the question asks for any pair.

The same stress test:

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q) {
    int x = *(const int *)p, y = *(const int *)q;
    return (x > y) - (x < y);
}

int a[300000];

int main() {
    int n, t;
    scanf("%d %d", &n, &t);
    for (int i = 0; i < n; i++) a[i] = 2 * i;
    qsort(a, n, sizeof(int), cmp);
    int l = 0, r = n - 1;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == t) {
            printf("%d + %d = %d\n", a[l], a[r], t);
            return 0;
        }
        if (s < t) l++;
        else r--;
    }
    printf("no pair\n");
    return 0;
}

Input 300000 7:

no pair

Complexity: sorting O(n log n) + the walk O(n) = O(n log n) time, O(1) extra space (qsort sorts in place).

If you need the original indexes (the LeetCode version of two sum asks for them), sorting loses them. Sort an array of structs {value, index} instead, or (in other languages) use a hash map for O(n) average. Plain C has no built-in hash map.

Q2: Count pairs with a given sum

Problem. Read n and a sum k, then n integers. Count the pairs i < j with a[i] + a[j] == k.

Input Output
5 6 / 1 5 7 -1 5 3 pairs (1 + first 5, 1 + second 5, 7 + -1)
4 4 / 2 2 2 2 6 pairs (any two of the four 2s: 4 × 3 / 2)
5 4 / 1 1 3 3 3 6 pairs (2 ones × 3 threes)
3 100 / 1 2 3 0 pairs

Edge cases: repeated values, all equal, no pair, counts too big for an int.

The obvious attempt: reuse two sum, count, move both pointers

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q) {
    int x = *(const int *)p, y = *(const int *)q;
    return (x > y) - (x < y);
}
int main() {
    int n, k, a[100];
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    qsort(a, n, sizeof(int), cmp);
    int l = 0, r = n - 1, count = 0;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == k) {
            count++;
            l++;
            r--;
        }
        else if (s < k) l++;
        else r--;
    }
    printf("%d pairs\n", count);
    return 0;
}

Input 5 6 / 1 5 7 -1 5:

2 pairs

Why: copies of a value make more pairs

sorted: -1 1 5 5 7
l=0 r=4: -1 + 7 = 6  count = 1, l=1 r=3
l=1 r=3:  1 + 5 = 6  count = 2, l=2 r=2  -> loop ends

The 1 also pairs with the other 5 (index 2), and that pair is never counted. Moving both pointers threw away copies.

The fix: count the copies on both sides

On a match there are two cases:

  • a[l] != a[r]: count cl = copies of a[l] and cr = copies of a[r]. Every left copy pairs with every right copy: cl × cr pairs. Then jump past all of them.
  • a[l] == a[r]: then every value from l to r is the same (the array is sorted). m = r - l + 1 equal values make m(m - 1)/2 pairs (choose 2 of m), and we are done.

The inner while (a[l + cl] == a[l]) loops stay inside the array: they stop at the latest at a[r], which is different.

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q) {
    int x = *(const int *)p, y = *(const int *)q;
    return (x > y) - (x < y);
}
int main() {
    int n, k, a[100];
    scanf("%d %d", &n, &k);
    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]);
    qsort(a, n, sizeof(int), cmp);
    int l = 0, r = n - 1, count = 0;
    while (l < r) {
        int s = a[l] + a[r];
        if (s < k) l++;
        else if (s > k) r--;
        else if (a[l] == a[r]) {
            int m = r - l + 1;
            count += m * (m - 1) / 2;
            break;
        } else {
            int cl = 1, cr = 1;
            while (a[l + cl] == a[l]) cl++;
            while (a[r - cr] == a[r]) cr++;
            count += cl * cr;
            l += cl;
            r -= cr;
        }
    }
    printf("%d pairs\n", count);
    return 0;
}

Input 5 6 / 1 5 7 -1 5:

3 pairs

Input 4 4 / 2 2 2 2:

6 pairs

Input 5 4 / 1 1 3 3 3:

6 pairs

Input 3 100 / 1 2 3:

0 pairs

Stress test: the count overflows an int

100,000 values, all 2, k = 4. The right answer is 100,000 × 99,999 / 2 = 4,999,950,000.

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q) {
    int x = *(const int *)p, y = *(const int *)q;
    return (x > y) - (x < y);
}
int a[100000];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) a[i] = 2;
    qsort(a, n, sizeof(int), cmp);
    int l = 0, r = n - 1, count = 0;
    while (l < r) {
        int s = a[l] + a[r];
        if (s < k) l++;
        else if (s > k) r--;
        else if (a[l] == a[r]) {
            int m = r - l + 1;
            count += m * (m - 1) / 2;
            break;
        } else {
            int cl = 1, cr = 1;
            while (a[l + cl] == a[l]) cl++;
            while (a[r - cr] == a[r]) cr++;
            count += cl * cr;
            l += cl;
            r -= cr;
        }
    }
    printf("%d pairs\n", count);
    return 0;
}

Input 100000 4:

704982704 pairs

m * (m - 1) is 9,999,900,000, far above INT_MAX (2,147,483,647). Signed overflow is undefined behaviour: the C standard makes no promise about what happens. This build printed a wrong number. Count in long long, print with %lld, and cast before multiplying so the multiplication itself is done in long long:

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q) {
    int x = *(const int *)p, y = *(const int *)q;
    return (x > y) - (x < y);
}
int a[100000];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) a[i] = 2;
    qsort(a, n, sizeof(int), cmp);
    int l = 0, r = n - 1;
    long long count = 0;
    while (l < r) {
        int s = a[l] + a[r];
        if (s < k) l++;
        else if (s > k) r--;
        else if (a[l] == a[r]) {
            int m = r - l + 1;
            count += (long long)m * (m - 1) / 2;
            break;
        } else {
            int cl = 1, cr = 1;
            while (a[l + cl] == a[l]) cl++;
            while (a[r - cr] == a[r]) cr++;
            count += (long long)cl * cr;
            l += cl;
            r -= cr;
        }
    }
    printf("%lld pairs\n", count);
    return 0;
}

Input 100000 4:

4999950000 pairs

The small-input solution with long long (the full answer to Q2):

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q) {
    int x = *(const int *)p, y = *(const int *)q;
    return (x > y) - (x < y);
}

int main() {
    int n, k, a[100];
    scanf("%d %d", &n, &k);
    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]);
    qsort(a, n, sizeof(int), cmp);
    int l = 0, r = n - 1;
    long long count = 0;
    while (l < r) {
        int s = a[l] + a[r];
        if (s < k) l++;
        else if (s > k) r--;
        else if (a[l] == a[r]) {
            int m = r - l + 1;
            count += (long long)m * (m - 1) / 2;
            break;
        } else {
            int cl = 1, cr = 1;
            while (a[l + cl] == a[l]) cl++;
            while (a[r - cr] == a[r]) cr++;
            count += (long long)cl * cr;
            l += cl;
            r -= cr;
        }
    }
    printf("%lld pairs\n", count);
    return 0;
}

Input 5 6 / 1 5 7 -1 5:

3 pairs

Input 4 4 / 2 2 2 2:

6 pairs

Input 1 5 / 5:

0 pairs

Complexity: O(n log n) for the sort, O(n) for the walk (every element is passed once by l or r): O(n log n) time, O(1) extra space.

Q3: Move all zeros to the end

Problem. Read n, then n integers. Move every 0 to the end in place, keeping the order of the non-zero values.

Input Output
5 / 0 1 0 3 12 1 3 12 0 0
3 / 0 0 0 0 0 0
4 / -2 7 5 -9 -2 7 5 -9
6 / 0 4 0 0 6 0 4 6 0 0 0 0

Edge cases: all zeros, no zeros, zeros already at the end, n = 1.

The obvious attempt: swap each zero with the last element

#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int last = n - 1;
    for (int i = 0; i < last; i++) {
        if (a[i] == 0) {
            int tmp = a[i];
            a[i] = a[last];
            a[last] = tmp;
            last--;
        }
    }
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 5 / 0 1 0 3 12:

12 1 3 0 0 

The zeros are at the end, but 12 jumped to the front: a swap pulls the last value all the way forward, so the order breaks.

The fix: a write index k

Same read/write idea as episode 9: k is where the next non-zero value goes. For each i, if a[i] isn't 0, copy it to a[k] and k++. Then fill a[k] … a[n - 1] with zeros. Non-zero values are copied left in the order they come, so the order is kept (k <= i always, so nothing is overwritten before it is read).

The typo -Wall catches: if (a[i] = 0)

#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 k = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] = 0) continue;
        a[k] = a[i];
        k++;
    }
    for (; k < n; k++) a[k] = 0;
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

The compiler's warnings:

main.c: In function ‘main’:
main.c:13:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   13 |         if (a[i] = 0) continue;
      |             ^

Input 5 / 0 1 0 3 12:

0 0 0 0 0 

a[i] = 0 is an assignment: it sets a[i] to 0, and the value of the whole expression is 0, which is false. So nothing is skipped and every element (now 0) is copied: all zeros. == compares. The program compiled, and only the warning told us: -Wall turns on warnings like this one, so always compile with it and read every warning.

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 k = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) continue;
        a[k] = a[i];
        k++;
    }
    for (; k < n; k++) a[k] = 0;
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}
(no warnings)

Input 5 / 0 1 0 3 12:

1 3 12 0 0 

Input 3 / 0 0 0:

0 0 0 

Input 4 / -2 7 5 -9:

-2 7 5 -9 

Input 6 / 0 4 0 0 6 0:

4 6 0 0 0 0 

Input 1 / 0:

0 

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

Another way (one pass, with swaps). Swap a[i] with a[k] whenever a[i] != 0, then k++. This also keeps the order and needs no fill loop:

#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 k = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] != 0) {
            int tmp = a[i];
            a[i] = a[k];
            a[k] = tmp;
            k++;
        }
    }
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 5 / 0 1 0 3 12:

1 3 12 0 0 

Input 6 / 0 4 0 0 6 0:

4 6 0 0 0 0 

Complexity summary

Question Method Time Extra space
Two sum every pair (j from i + 1) O(n²) O(1)
qsort + two pointers O(n log n) O(1)
Count pairs two pointers, move both on a match O(n log n), wrong with repeats O(1)
two pointers + count copies (cl × cr, m(m - 1)/2) O(n log n) O(1)
every pair O(n²) O(1)
Move zeros swap with the last O(n), order broken O(1)
write index k + fill O(n) O(1)

Common mistakes (and the real results)

Mistake What you see Why Fix
for (int j = 0; j < n; j++) in two sum no error: 4 + 4 = 8 with one 4 an item is paired with itself start j at i + 1
checking every pair for 300,000 items Time Limit Exceeded about 45 billion pairs sort + two pointers
return x - y; in a comparator wrong order for far-apart values the subtraction overflows (x > y) - (x < y)
on a match: count++; l++; r--; no error: 2 pairs instead of 3 copies of a value are skipped count copies: cl × cr
int count, m * (m - 1) / 2 in int no error: 704982704 pairs (UB) the count passes INT_MAX long long count, cast before multiplying
swap each zero with the last element no error: 12 1 3 0 0 a swap moves the last value forward write index k, then fill
if (a[i] = 0) warning: suggest parentheses around assignment used as truth value [-Wparentheses], output all zeros = assigns, it doesn't compare if (a[i] == 0)

Your turn: three sum (solution)

Problem. Read n and a target t, then n integers. Print three different items that add up to t, or no triple. 1 4 6 8 10, t = 13 → 1 + 4 + 8. t = 30 → no triple.

Idea. Sort. Fix the first item a[i] with a loop, then run today's two pointers on the items after it (l = i + 1, r = n - 1) looking for t - a[i]. n loops of O(n) each: O(n²) instead of O(n³) for three nested loops, O(1) extra space.

Show the solution
#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q) {
    int x = *(const int *)p, y = *(const int *)q;
    return (x > y) - (x < y);
}

int main() {
    int n, t, a[100];
    scanf("%d %d", &n, &t);
    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]);
    qsort(a, n, sizeof(int), cmp);
    for (int i = 0; i < n - 2; i++) {
        int l = i + 1, r = n - 1;
        while (l < r) {
            int s = a[i] + a[l] + a[r];
            if (s == t) {
                printf("%d + %d + %d = %d\n", a[i], a[l], a[r], t);
                return 0;
            }
            if (s < t) l++;
            else r--;
        }
    }
    printf("no triple\n");
    return 0;
}

Input 5 13 / 1 4 6 8 10:

1 + 4 + 8 = 13

Input 5 30 / 1 4 6 8 10:

no triple

Input 6 0 / -1 0 1 2 -1 -4:

-1 + -1 + 2 = 0

Input 2 3 / 1 2:

no triple

Practice questions (with solutions)

1. Pair with a given difference. Read n and d ≥ 0, then n sorted integers. Print a pair with a[j] - a[i] == d (i < j), or no pair. Two pointers that both move forward: if the difference is too small, j++; too big, i++. O(n).

Solution
#include <stdio.h>

int main() {
    int n, d, a[100];
    scanf("%d %d", &n, &d);
    if (n < 1 || n > 100 || d < 0) {
        printf("need 1 <= n <= 100 and d >= 0\n");
        return 0;
    }
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int i = 0, j = 1;
    while (j < n) {
        int diff = a[j] - a[i];
        if (i != j && diff == d) {
            printf("%d - %d = %d\n", a[j], a[i], d);
            return 0;
        }
        if (i == j || diff < d) j++;
        else i++;
    }
    printf("no pair\n");
    return 0;
}

Input 6 78 / 2 3 5 10 50 80:

80 - 2 = 78

Input 4 45 / 1 8 30 40:

no pair

Input 3 0 / 4 4 7:

4 - 4 = 0

2. Move all negative numbers to the front, keeping the order of both groups. The same write index as Q3, but in two passes into a second array (keeping both orders in place in O(n) needs more advanced tricks).

Solution
#include <stdio.h>

int main() {
    int n, a[100], b[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 k = 0;
    for (int i = 0; i < n; i++)
        if (a[i] < 0) b[k++] = a[i];
    for (int i = 0; i < n; i++)
        if (a[i] >= 0) b[k++] = a[i];
    for (int i = 0; i < n; i++) printf("%d ", b[i]);
    printf("\n");
    return 0;
}

Input 6 / 3 -1 4 -5 0 -2:

-1 -5 -2 3 4 0 

Input 3 / 1 2 3:

1 2 3 

3. Count pairs whose sum is less than k. Sort, then two pointers: if a[l] + a[r] < k, then a[l] pairs with every element from l + 1 to r, so add r - l and l++; otherwise r--. O(n log n). Use long long for the count.

Solution
#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q) {
    int x = *(const int *)p, y = *(const int *)q;
    return (x > y) - (x < y);
}

int main() {
    int n, k, a[100];
    scanf("%d %d", &n, &k);
    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]);
    qsort(a, n, sizeof(int), cmp);
    int l = 0, r = n - 1;
    long long count = 0;
    while (l < r) {
        if (a[l] + a[r] < k) {
            count += r - l;
            l++;
        } else r--;
    }
    printf("%lld pairs\n", count);
    return 0;
}

Input 5 7 / 5 1 3 4 7:

3 pairs

Input 3 2 / 1 1 1:

0 pairs

Input 3 100 / 10 20 30:

3 pairs

Quick quiz

#include <stdio.h>

int main() {
    int a[] = {1, 2, 4, 7, 11};
    int l = 0, r = 4;
    while (a[l] + a[r] != 9) {
        if (a[l] + a[r] < 9) l++;
        else r--;
    }
    printf("%d %d\n", l, r);
    return 0;
}

(A) 1 3 (B) 2 3 (C) 0 3 (D) 1 4

Answer

(A) 1 3. 1 + 11 = 12 > 9 → r = 3. 1 + 7 = 8 < 9 → l = 1. 2 + 7 = 9 → stop.

Output:

1 3

Interview questions

  1. Solve two sum. What are the trade-offs? Brute force O(n²), O(1). Sort + two pointers O(n log n), O(1) (loses the original indexes unless you sort {value, index} structs). Hash map O(n) average, O(n) space.
  2. Why does the two-pointer method work? If the smallest plus the largest is too small, the smallest can't pair with anything, so it is dropped (and the mirror case for too big). Each step removes one candidate.
  3. Why does j start at i + 1? So an element is never paired with itself and every pair is checked once.
  4. What does a qsort comparator return, and why not x - y? Negative / zero / positive; x - y can overflow.
  5. Count pairs with sum k when values repeat. Count the copies on each side (cl × cr), and m(m - 1)/2 when both pointers hold the same value.
  6. How big can a pair count be? About n²/2: for n = 100,000 almost 5 billion, so long long.
  7. Move zeros to the end in O(n), O(1), keeping the order. A write index: copy non-zeros forward, then fill with zeros (or swap with a[k]).
  8. What is wrong with if (x = 0), and how do you catch it? It assigns instead of comparing; compile with -Wall and read the warnings.
  9. Extend two sum to three sum. Sort, fix one element, two pointers on the rest: O(n²).

Glossary

Term Meaning Example
Two sum Find two different elements whose sum is a target 4 + 3 = 7
Pair i < j Two different positions, each pair counted once (0, 3) but not (3, 0) or (0, 0)
Brute force Trying every possibility every pair i, j
Stress test A huge input, often made by the program, to test speed 300,000 prices
Time Limit Exceeded (TLE) The judge stopped a program that ran too long 8 seconds here
Sorting Putting elements in order, smallest first 4 1 6 3 → 1 3 4 6
qsort The C library's sort function, in <stdlib.h> qsort(a, n, sizeof(int), cmp)
Comparator A function telling the sort which of two elements goes first cmp returns -1, 0 or 1
void * A pointer to any type; must be cast before use *(const int *)p
const The value can't be changed through this name const void *p
Two pointers Two indexes moved through an array by simple rules l from the left, r from the right
Copies / runs Equal values next to each other in a sorted array 5 5 in -1 1 5 5 7
m(m - 1)/2 The number of ways to choose 2 of m things 4 twos → 6 pairs
Signed overflow A signed result too big for its type: undefined behaviour 100000 * 99999 in int
Undefined behaviour (UB) The C standard makes no promise about what happens overflow, an index out of range
long long An integer of at least 64 bits up to about 9.2 × 10¹⁸
Cast Converting a value to another type (long long)m * (m - 1)
%lld The printf format for long long printf("%lld", count)
In place Changing the array itself with O(1) extra space moving zeros with k
Write index An index marking where the next kept value goes k in Q3
Order kept (stable) Equal-ranked items keep their original order 1 3 12 stays 1 3 12
= vs == Assignment vs comparison a[i] = 0 sets, a[i] == 0 tests
-Wall gcc flag that turns on the common warnings -Wparentheses
Warning A message about suspicious code; the program still compiles "suggest parentheses around assignment"
O(n log n) Slightly more than linear; good sorting algorithms qsort
O(n²) Double the input, four times the work a loop inside a loop

Summary

  • Two sum: brute force with j from i + 1 is O(n²) and times out on big inputs; sort with qsort and a safe comparator, then walk two pointers from both ends: O(n log n).
  • Count pairs: on a match, count the copies on both sides (cl × cr, or m(m - 1)/2 when the values are equal), and keep the count in long long.
  • Move zeros: a write index k keeps the order; swapping with the last element breaks it.
  • if (a[i] = 0) compiles but is wrong; -Wall warns about it. Read every warning.

Next episode: Array questions V: merging two sorted arrays, union and intersection of sorted arrays, and the maximum subarray sum with Kadane's algorithm (and the all-negative case).