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
- Sort the prices, smallest first.
l = 0points at the cheapest item,r = n - 1at the costliest. (A pointer here is just an index we move.)sum = a[l] + a[r]: -sum == t: found. -sum < t: we need more, sol++(a costlier cheap item). -sum > t: too much, sor--(drop the costliest).- Stop when
lmeetsr: 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]: countcl= copies ofa[l]andcr= copies ofa[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 fromltoris the same (the array is sorted).m = r - l + 1equal 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
- 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. - 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.
- Why does
jstart ati + 1? So an element is never paired with itself and every pair is checked once. - What does a qsort comparator return, and why not
x - y? Negative / zero / positive;x - ycan overflow. - Count pairs with sum k when values repeat. Count the copies on each side (
cl × cr), andm(m - 1)/2when both pointers hold the same value. - How big can a pair count be? About n²/2: for n = 100,000 almost 5 billion, so
long long. - 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]). - What is wrong with
if (x = 0), and how do you catch it? It assigns instead of comparing; compile with-Walland read the warnings. - 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
jfromi + 1is O(n²) and times out on big inputs; sort withqsortand 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, orm(m - 1)/2when the values are equal), and keep the count inlong long. - Move zeros: a write index
kkeeps the order; swapping with the last element breaks it. if (a[i] = 0)compiles but is wrong;-Wallwarns 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).