These are the notes for C Coding Questions, episode 9, placement practice for people who finished the SyntaxPilot C course. Array questions, part three: remove duplicates from a sorted array in place, the frequency of each element (a done array, and a counting array), and the missing number from 1 to n (the sum formula in long long, and the XOR trick).
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 school attendance register
| In the register | In C |
|---|---|
| the same roll number written twice; in a sorted list the copies sit together | remove duplicates from a sorted array |
| how many days was each student present? a tally per student | the frequency of each element: how many times it appears |
| roll numbers 1 to 40, only 39 names today: who is absent? | the missing number in 1..n |
Q1: Remove duplicates from a sorted array
Problem. Read n, then n integers in sorted (non-decreasing) order. Remove the duplicates in place: the unique values must end up at the front of the same array. Print how many there are, then the values.
| Input | Output |
|---|---|
6 / 1 1 2 2 2 3 |
3 unique: 1 2 3 |
4 / 5 5 5 5 |
1 unique: 5 |
4 / -3 0 4 9 |
4 unique: -3 0 4 9 |
1 / 8 |
1 unique: 8 |
Edge cases: three or more copies in a row, all equal, no copies, n = 1.
The obvious attempt: shift left on every duplicate
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 1; i < n; i++) {
if (a[i] == a[i - 1]) {
for (int j = i; j < n - 1; j++) a[j] = a[j + 1];
n--;
}
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Input 4 1 1 2 3:
1 2 3
Input 5 1 1 1 2 3:
1 1 2 3
Why: the shift skips an element
1 1 1 2 3, i = 1: a[1] == a[0] -> shift -> 1 1 2 3 (another 1 slid into a[1]), n = 4
i = 2: a[2] = 2 vs a[1] = 1 -> fine (a[1] is never checked again)
After a shift, i moves on and skips the value that slid into place. (Not moving i after a shift would fix the answer, but every shift moves up to n elements, so the whole thing is O(n²).)
The fix: two pointers, read with i and write with k
kis the number of unique values kept so far, and also where the next one is written.a[0]is always kept, sok = 1.ireads every element. Ifa[i]differs from the last kept valuea[k - 1], write it ata[k]and increasek.- Because the array is sorted, all copies of a value are next to each other, so comparing with the last kept value is enough.
1 1 1 2 3, k = 1
i = 1: 1 == a[0] -> skip
i = 2: 1 == a[0] -> skip
i = 3: 2 != a[0] -> a[1] = 2, k = 2
i = 4: 3 != a[1] -> a[2] = 3, k = 3 -> 1 2 3 | (2 3 left behind, ignored)
#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 = 1;
for (int i = 1; i < n; i++) {
if (a[i] != a[k - 1]) {
a[k] = a[i];
k++;
}
}
printf("%d unique: ", k);
for (int i = 0; i < k; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Input 5 1 1 1 2 3:
3 unique: 1 2 3
Input 6 1 1 2 2 2 3:
3 unique: 1 2 3
Input 4 5 5 5 5:
1 unique: 5
Input 4 -3 0 4 9:
4 unique: -3 0 4 9
Input 1 8:
1 unique: 8
Complexity: one pass, O(n) time, O(1) extra space.
Q2: Frequency of each element
Problem. Read n, then n integers in any order. Print every distinct value once, with how many times it appears (its frequency).
| Input | Output |
|---|---|
6 / 10 20 10 30 20 10 |
10: 3 times, 20: 2 times, 30: 1 time |
3 / 7 7 7 |
7: 3 times |
The obvious attempt: count every element
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++)
if (a[j] == a[i]) count++;
printf("%d appears %d times\n", a[i], count);
}
return 0;
}
Input 6 10 20 10 30 20 10:
10 appears 3 times
20 appears 2 times
10 appears 3 times
30 appears 1 times
20 appears 2 times
10 appears 3 times
Every copy of 10 counts all the 10s again and prints again: six lines for three values.
Fix 1: a done array (any values)
done[i] is a flag: 1 once element i has been counted. int done[100] = {0}; sets every element to 0 (when an array initializer is shorter than the array, the rest are zeros). For each element not yet done, count its copies from i onwards and mark them all done.
#include <stdio.h>
int main() {
int n, a[100], done[100] = {0};
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]);
for (int i = 0; i < n; i++) {
if (done[i]) continue;
int count = 0;
for (int j = i; j < n; j++) {
if (a[j] == a[i]) {
count++;
done[j] = 1;
}
}
printf("%d appears %d times\n", a[i], count);
}
return 0;
}
Input 6 10 20 10 30 20 10:
10 appears 3 times
20 appears 2 times
30 appears 1 times
Input 3 7 7 7:
7 appears 3 times
Input 4 -1 5 -1 5:
-1 appears 2 times
5 appears 2 times
Input 1 42:
42 appears 1 times
Complexity: a loop inside a loop: O(n²) time; the done array is O(n) extra space. It works for any values, including negatives and huge ones.
Fix 2: a counting array (small values)
When the values come from a small range, like exam marks from 0 to 100, use the value itself as an index: freq[x] counts how many times x appeared. One pass to count, one pass over the 101 possible values to print. Check the value first: freq[150] would write past the end of a 101-element array (undefined behaviour).
#include <stdio.h>
int main() {
int n, x, freq[101] = {0};
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &x);
if (x < 0 || x > 100) {
printf("marks must be 0 to 100\n");
return 0;
}
freq[x]++;
}
for (int v = 0; v <= 100; v++)
if (freq[v] > 0) printf("%d appears %d times\n", v, freq[v]);
return 0;
}
Input 6 10 20 10 30 20 10:
10 appears 3 times
20 appears 2 times
30 appears 1 times
Input 5 0 100 0 100 55:
0 appears 2 times
55 appears 1 times
100 appears 2 times
Input 3 90 150 90:
marks must be 0 to 100
Complexity: O(n + range) time and O(range) space, where the range is the number of possible values (101 here). The output comes in increasing order of value. For values up to a billion, the counting array would be far too big: use the done array, or sort first (O(n log n)) and count runs of equal values.
Q3: The missing number
Problem. Read n, then n − 1 distinct numbers from 1 to n, in any order. Exactly one number from 1 to n is missing. Print it.
| Input | Output |
|---|---|
5 / 1 2 4 5 |
3 |
5 / 2 3 4 5 |
1 |
5 / 4 1 3 2 |
5 |
1 / (nothing) |
1 |
Edge cases: the first number missing, the last number missing, n = 1, a very big n.
The obvious attempt: search for every k
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n - 1; i++) scanf("%d", &a[i]);
for (int k = 1; k <= n; k++) {
int found = 0;
for (int i = 0; i < n - 1; i++)
if (a[i] == k) { found = 1; break; }
if (!found) printf("missing %d\n", k);
}
return 0;
}
Input 5 1 2 4 5:
missing 3
A stress test: the same search on 300,000 roll numbers. The program makes the numbers itself (1 to n, skipping m), because typing 300,000 numbers isn't practical; the global array a lives outside main, so its size doesn't matter for the stack.
#include <stdio.h>
int a[300000];
int main() {
int n, m;
scanf("%d %d", &n, &m);
int len = 0;
for (int v = 1; v <= n; v++)
if (v != m) a[len++] = v;
for (int k = 1; k <= n; k++) {
int found = 0;
for (int i = 0; i < len; i++)
if (a[i] == k) { found = 1; break; }
if (!found) printf("missing %d\n", k);
}
return 0;
}
Input 300000 299999:
Time Limit Exceeded (stopped after 8 seconds)
Why, and the sum idea
n searches, each up to n steps: O(n²), about 45 billion steps for n = 300,000.
We know what the total should be: 1 + 2 + … + n = n(n + 1) / 2 (pair 1 with n, 2 with n − 1, …: n/2 pairs, each adding to n + 1). So missing = n(n + 1)/2 − (sum of the array). For n = 5: 15 − (1 + 2 + 4 + 5) = 3.
#include <stdio.h>
int a[300000];
int main() {
int n, m;
scanf("%d %d", &n, &m);
int len = 0;
for (int v = 1; v <= n; v++)
if (v != m) a[len++] = v;
int total = n * (n + 1) / 2;
int sum = 0;
for (int i = 0; i < len; i++) sum = sum + a[i];
printf("missing %d\n", total - sum);
return 0;
}
Input 200000 123456:
missing -2147360192
Why: n(n + 1) overflowed
200,000 × 200,001 = 40,000,200,000, far above INT_MAX (2,147,483,647). That is signed overflow, undefined behaviour; this build printed a negative roll number. (For n = 100,000 this build happened to print the right answer: undefined behaviour can also look right, which is why it is dangerous.)
Fix A: long long. Cast before multiplying: (long long)n * (n + 1) makes the multiplication itself happen in long long. (long long)(n * (n + 1)) would be too late.
#include <stdio.h>
int a[300000];
int main() {
int n, m;
scanf("%d %d", &n, &m);
int len = 0;
for (int v = 1; v <= n; v++)
if (v != m) a[len++] = v;
long long total = (long long)n * (n + 1) / 2;
long long sum = 0;
for (int i = 0; i < len; i++) sum = sum + a[i];
printf("missing %lld\n", total - sum);
return 0;
}
Input 200000 123456:
missing 123456
Input 300000 299999:
missing 299999
Fix B: the XOR trick
From episode 6: XOR (^) gives 1 where the bits differ. Two rules follow:
x ^ x = 0(nothing differs) andx ^ 0 = x;- the order doesn't matter:
a ^ b ^ a = b.
XOR together all numbers from 1 to n and all numbers in the input. Every present number appears twice and cancels; only the missing one is left. XOR works bit by bit with no carry, so it can never overflow. And the numbers don't even need to be stored.
n = 5: (1 ^ 2 ^ 3 ^ 4 ^ 5) ^ (1 ^ 2 ^ 4 ^ 5) = 3
#include <stdio.h>
int main() {
int n, x;
scanf("%d", &n);
if (n < 1) {
printf("n must be 1 or more\n");
return 0;
}
int r = 0;
for (int v = 1; v <= n; v++) r = r ^ v;
for (int i = 0; i < n - 1; i++) {
scanf("%d", &x);
r = r ^ x;
}
printf("missing %d\n", r);
return 0;
}
Input 5 1 2 4 5:
missing 3
Input 5 2 3 4 5:
missing 1
Input 5 4 1 3 2:
missing 5
Input 1:
missing 1
Input 0:
n must be 1 or more
The XOR version on the stress test that overflowed:
#include <stdio.h>
int a[300000];
int main() {
int n, m;
scanf("%d %d", &n, &m);
int len = 0;
for (int v = 1; v <= n; v++)
if (v != m) a[len++] = v;
int r = 0;
for (int v = 1; v <= n; v++) r = r ^ v;
for (int i = 0; i < len; i++) r = r ^ a[i];
printf("missing %d\n", r);
return 0;
}
Input 200000 123456:
missing 123456
Complexity: both fixes are O(n) time and O(1) extra space (the input version of XOR stores nothing).
Complexity summary
| Question | Method | Time | Extra space |
|---|---|---|---|
| Remove duplicates | shift on every copy | O(n²) (and wrong as written) | O(1) |
read with i, write with k |
O(n) | O(1) | |
| Frequency | count every element | O(n²), repeats lines | O(1) |
| done array | O(n²) | O(n) | |
| counting array | O(n + range) | O(range) | |
| sort, then count runs | O(n log n) | O(1) | |
| Missing number | search for every k | O(n²) | O(1) |
sum formula in long long |
O(n) | O(1) | |
| XOR | O(n) | O(1) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
shift left on a duplicate, then i++ |
no error: 1 1 2 3 for 1 1 1 2 3 |
the value that slid in is never checked | read with i, write with k |
| print the count for every element | no error: 10 appears 3 times printed 3 times |
every copy reports again | a done array, or freq[x]++ |
freq[x]++ with x out of range |
no error: writes past the end (UB) | x is not a valid index |
check 0 <= x <= 100 first |
int total = n * (n + 1) / 2; |
no error: missing -2147360192 for n = 200,000 |
n(n + 1) overflows an int |
(long long)n * (n + 1) / 2, or XOR |
(long long)(n * (n + 1)) |
the same wrong answer | the cast comes after the overflow | cast n before multiplying |
| search for every k from 1 to n | Time Limit Exceeded |
O(n²) | sum or XOR |
Your turn: the single number (solution)
Problem. Read an odd n, then n integers where every value appears exactly twice except one, which appears once. Print it. 4 1 2 1 2 → 4. -5 3 3 → -5.
Idea. The quiz: XOR everything. Pairs cancel, the single value is left. O(n) time, O(1) space, nothing stored.
Show the solution
#include <stdio.h>
int main() {
int n, x, r = 0;
scanf("%d", &n);
if (n < 1 || n % 2 == 0) {
printf("n must be odd\n");
return 0;
}
for (int i = 0; i < n; i++) {
scanf("%d", &x);
r = r ^ x;
}
printf("appears once: %d\n", r);
return 0;
}
Input 5 4 1 2 1 2:
appears once: 4
Input 3 -5 3 3:
appears once: -5
Input 1 0:
appears once: 0
Input 4 1 1 2 2:
n must be odd
Practice questions (with solutions)
1. Remove duplicates from a sorted array, but allow each value at most twice. Same two pointers; compare with a[k - 2], the value two places back.
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 (k < 2 || a[i] != a[k - 2]) {
a[k] = a[i];
k++;
}
}
printf("%d kept: ", k);
for (int i = 0; i < k; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Input 8 1 1 1 2 2 2 3 3:
6 kept: 1 1 2 2 3 3
Input 4 5 5 5 5:
2 kept: 5 5
Input 3 1 2 3:
3 kept: 1 2 3
2. The most frequent mark (0 to 100); the smallest one if there is a tie. A counting array, then the index with the biggest count.
Solution
#include <stdio.h>
int main() {
int n, x, freq[101] = {0};
scanf("%d", &n);
if (n < 1) {
printf("n must be 1 or more\n");
return 0;
}
for (int i = 0; i < n; i++) {
scanf("%d", &x);
if (x < 0 || x > 100) {
printf("marks must be 0 to 100\n");
return 0;
}
freq[x]++;
}
int best = 0;
for (int v = 1; v <= 100; v++)
if (freq[v] > freq[best]) best = v;
printf("most frequent mark %d (%d times)\n", best, freq[best]);
return 0;
}
Input 7 70 85 70 90 85 70 40:
most frequent mark 70 (3 times)
Input 3 50 60 50:
most frequent mark 50 (2 times)
Input 2 10 20:
most frequent mark 10 (1 times)
3. The repeated number. Read n, then n + 1 numbers from 1 to n where exactly one value appears twice. XOR of 1..n and of the input leaves the repeated value.
Solution
#include <stdio.h>
int main() {
int n, x, r = 0;
scanf("%d", &n);
if (n < 1) {
printf("n must be 1 or more\n");
return 0;
}
for (int v = 1; v <= n; v++) r = r ^ v;
for (int i = 0; i < n + 1; i++) {
scanf("%d", &x);
r = r ^ x;
}
printf("repeated %d\n", r);
return 0;
}
Input 4 1 3 4 2 3:
repeated 3
Input 5 5 1 2 5 3 4:
repeated 5
Input 1 1 1:
repeated 1
Quick quiz
int r = 0;
int a[] = {4, 7, 4, 9, 7};
for (int i = 0; i < 5; i++) r = r ^ a[i];
printf("%d\n", r);
(A) 9 (B) 0 (C) 31 (D) 7
Answer
(A) 9. The two 4s cancel and the two 7s cancel (x ^ x = 0), so only 9 is left.
Output:
9
Interview questions
- Remove duplicates from a sorted array in O(n), O(1). Two pointers: read with
i, write withk, copy whena[i] != a[k - 1]; returnk. - What if the array is not sorted? Sort first (O(n log n)), or use a hash set (O(n) average, O(n) space; not built into C).
- Count the frequency of each element. Small range: a counting array, O(n + range). Otherwise sort and count runs, or a done array (O(n²)).
- Find the missing number from 1..n. Sum formula (in
long long) or XOR; both O(n), O(1). - Why is XOR safer than the sum? It can't overflow, whatever n is.
- Every element appears twice except one; find it. XOR of all elements.
- What does
int done[100] = {0};do? Initializes all 100 elements to 0. - Why must you check a value before
freq[x]++? An index outside the array is undefined behaviour.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Duplicate | A value that appears more than once | the second 1 in 1 1 2 |
| Sorted (non-decreasing) | Each element ≥ the one before | 1 1 2 3 |
| In place | Changing the array itself with O(1) extra space | dedup with i and k |
| Two pointers | Two indexes moving through the array | i reads, k writes |
| Read / write pointer | One index that reads every element, one that marks where to write | i, k |
| Frequency | How many times a value appears | 10 appears 3 times |
| Flag | A variable that remembers whether something happened | done[j] = 1 |
| Array initializer | Values in braces; missing ones become 0 | int done[100] = {0}; |
| Counting array | An array indexed by value, holding counts | freq[x]++ |
| Range | How many possible values there are | marks 0..100: 101 |
| Missing number | The one value of 1..n not in the input | 1 2 4 5 → 3 |
| Sum formula | 1 + 2 + … + n = n(n + 1)/2 | n = 5 → 15 |
XOR ^ |
1 where the bits differ; x ^ x = 0 |
4 ^ 7 ^ 4 = 7 |
| Stress test | A big input to test speed and correctness | 300,000 numbers |
| Global array | Declared outside every function | int a[300000]; |
| Signed overflow | A signed result too big for its type: undefined behaviour | 200000 * 200001 in int |
| Cast | Converting a value to another type | (long long)n |
long long |
An integer of at least 64 bits | up to about 9.2 × 10¹⁸ |
| Undefined behaviour (UB) | The C standard doesn't define what happens | overflow, freq[150] |
| O(n²) | Double the input, four times the work | a loop inside a loop |
| O(n + range) | Grows with the input size plus the number of possible values | counting sort |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | 8 seconds here |
Summary
- Remove duplicates from a sorted array with a read pointer
iand a write pointerk; compare with the last kept value. O(n), O(1). - Frequencies: a done array works for any values (O(n²)); a counting array is O(n + range) when the values are small; check the value before using it as an index.
- Missing number: n(n + 1)/2 minus the sum, computed in
long long; or XOR everything, where pairs cancel and nothing can overflow. - Searching for every value is O(n²): a stress test shows it.
Next episode: Array questions IV: two-sum (brute force vs sort + two pointers), counting pairs with a given sum, and moving all zeros to the end while keeping the order.