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

Array questions III

remove duplicates from a sorted arrayfrequency of each elementfind the missing number 1..n (sum and XOR ways)

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

  • k is the number of unique values kept so far, and also where the next one is written. a[0] is always kept, so k = 1.
  • i reads every element. If a[i] differs from the last kept value a[k - 1], write it at a[k] and increase k.
  • 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) and x ^ 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

  1. Remove duplicates from a sorted array in O(n), O(1). Two pointers: read with i, write with k, copy when a[i] != a[k - 1]; return k.
  2. 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).
  3. 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²)).
  4. Find the missing number from 1..n. Sum formula (in long long) or XOR; both O(n), O(1).
  5. Why is XOR safer than the sum? It can't overflow, whatever n is.
  6. Every element appears twice except one; find it. XOR of all elements.
  7. What does int done[100] = {0}; do? Initializes all 100 elements to 0.
  8. 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 i and a write pointer k; 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.