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

Vector questions II

remove duplicates from a sorted vector (erase-unique idiom)missing number 1..n (sum overflow, XOR)majority element (Boyer-Moore voting)

These are the notes for C++ Coding Questions, episode 9, placement practice for people who finished the SyntaxPilot C++ course. Vectors, part two: removing duplicates from a sorted vector (what std::unique really does, and the erase-unique idiom), the missing number from 1 to n (the sum formula, int overflow, and the XOR trick), and the majority element (Boyer-Moore voting, and why the candidate must be checked).

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 g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 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, TLE), like an online judge.

Some programs read a token first: typing big makes a test helper build a large input, because nobody can type 200,000 numbers.

Real-life pictures

In real life In C++
A clerk copies the different names to the top of a sorted list but never tears the bottom of the page off std::unique moves the keepers to the front and returns the new end; erase cuts the rest
Roll numbers 1..5, one student absent: 15 − (1 + 2 + 4 + 5) = 3 expected sum − actual sum
A car odometer at 99999 rolls over to 00000 int overflow (signed overflow is undefined behaviour)
Pair each roll number on the register with a student who answered; the unpaired number is absent XOR: a ^ a = 0, pairs cancel
An election where one name has more than half the votes: pair a vote for it with a vote for anyone else and throw both away; it always survives Boyer-Moore voting
But some slip always survives, majority or not check the candidate with a second count

Q1: Remove duplicates from a sorted vector

Problem. Read a sorted vector; remove repeated values in place; print the new size and the values.

Input Output
1 1 2 3 3 3: 1 2 3
1 1 1 1 2 2 2: 1 2
4 5 6 3: 4 5 6
(empty) 0:

The obvious attempt: call std::unique

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        unique(v.begin(), v.end());
        cout << v.size() << ": ";
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Output:

5: 1 2 3 3 3 
6: 1 2 1 1 2 2 
3: 4 5 6 
0: 

Wrong: the size never changed and the end is junk. An algorithm like unique works through iterators (positions); it can move elements but cannot change the container's size. It moves the first element of every run of equal values to the front and returns an iterator to the new logical end. Whatever lies after that iterator is left in a valid but unspecified state.

The idea underneath: a write index

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        int k = 0;
        for (int i = 0; i < n; i++)
            if (k == 0 || v[i] != v[k - 1]) v[k++] = v[i];
        v.resize(k);
        cout << v.size() << ": ";
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Output:

3: 1 2 3 
2: 1 2 
3: 4 5 6 
0: 

Keep v[i] only if it differs from the last kept value v[k - 1] (in a sorted vector, equal values are always neighbours), then resize(k). O(n) time, O(1) extra space.

The library: the erase-unique idiom

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        v.erase(unique(v.begin(), v.end()), v.end());
        cout << v.size() << ": ";
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Same output. unique returns the new end; erase(newEnd, v.end()) cuts off the leftovers. On an unsorted vector, unique only removes adjacent repeats, so sort first if the order doesn't matter.

Q2: The missing number from 1 to n

Problem. Read n, then n − 1 different numbers from 1..n; print the missing one.

Input Output
n = 5: 1 2 4 5 3
n = 3: 2 3 1
n = 1: (nothing) 1
big: n = 200,000, every number but 123456 123456

The obvious attempt: sums in int

#include <iostream>
#include <string>
using namespace std;

int main() {
    string first;
    while (cin >> first) {
        int n, sum = 0;
        if (first == "big") {               // test: n = 200000, every number but 123456
            n = 200000;
            for (int x = 1; x <= n; x++) if (x != 123456) sum += x;
        } else {
            n = stoi(first);
            for (int i = 0; i < n - 1; i++) { int x; cin >> x; sum += x; }
        }
        int expected = n * (n + 1) / 2;
        cout << "missing " << expected - sum << "\n";
    }
    return 0;
}

Output:

missing 3
missing 1
missing 1
missing -2147360192

Wrong for big: 200,000 × 200,001 = 40,000,200,000, far more than INT_MAX (2,147,483,647). Signed overflow is undefined behaviour; here the value wrapped around, and dividing the wrapped value by 2 made the final difference wrong. (With some other n the wrap-arounds happen to cancel and the answer looks right, which is exactly why overflow bugs survive testing.)

Fix 1: long long, cast before multiplying

#include <iostream>
#include <string>
using namespace std;

int main() {
    string first;
    while (cin >> first) {
        int n;
        long long sum = 0;
        if (first == "big") {               // test: n = 200000, every number but 123456
            n = 200000;
            for (int x = 1; x <= n; x++) if (x != 123456) sum += x;
        } else {
            n = stoi(first);
            for (int i = 0; i < n - 1; i++) { int x; cin >> x; sum += x; }
        }
        long long expected = (long long)n * (n + 1) / 2;
        cout << "missing " << expected - sum << "\n";
    }
    return 0;
}

Output:

missing 3
missing 1
missing 1
missing 123456

(long long)n * (n + 1) converts n first, so the multiplication itself happens in 64 bits. (long long)(n * (n + 1)) would be too late: the overflow already happened inside the brackets.

Fix 2: XOR

#include <iostream>
#include <string>
using namespace std;

int main() {
    string first;
    while (cin >> first) {
        int n, x_all = 0, x_seen = 0;
        if (first == "big") {               // test: n = 200000, every number but 123456
            n = 200000;
            for (int x = 1; x <= n; x++) if (x != 123456) x_seen ^= x;
        } else {
            n = stoi(first);
            for (int i = 0; i < n - 1; i++) { int x; cin >> x; x_seen ^= x; }
        }
        for (int x = 1; x <= n; x++) x_all ^= x;
        cout << "missing " << (x_all ^ x_seen) << "\n";
    }
    return 0;
}

Same output. XOR every number from 1 to n, and every input; each present number appears twice and cancels (a ^ a = 0, a ^ 0 = a, order doesn't matter), leaving the missing one. No value ever exceeds n, so there is nothing to overflow. O(n) time, O(1) space for both fixes.

Q3: The majority element

Problem. Print the value that appears more than n / 2 times, or −1 if there is none.

Input Output
2 2 1 1 1 2 2 2 (4 of 7)
3 3 4 3
9 9
1 2 3 −1
1 1 2 2 −1 (exactly half is not more than half)
big: 149,999 different numbers, then 150,001 sevens 7

The obvious attempt: count every element

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> readCase(const string& first) {
    if (first == "big") {   // test: 149,999 different numbers, then 150,001 sevens
        vector<int> v;
        for (int i = 0; i < 149999; i++) v.push_back(100 + i);
        for (int i = 0; i < 150001; i++) v.push_back(7);
        return v;
    }
    vector<int> v(stoi(first));
    for (int& x : v) cin >> x;
    return v;
}

int main() {
    string first;
    while (cin >> first) {
        vector<int> v = readCase(first);
        int n = v.size(), answer = -1;
        for (int i = 0; i < n && answer == -1; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (v[j] == v[i]) count++;
            if (count > n / 2) answer = v[i];
        }
        cout << "majority " << answer << "\n";
    }
    return 0;
}

Small tests:

majority 2
majority 3
majority 9

big: Time Limit Exceeded. The majority sits at the end, so about 150,000 elements are each counted across all 300,000: 45 billion steps.

Boyer-Moore voting

Keep a candidate and votes = 0. For each x: if votes == 0, x becomes the candidate; then x == candidate adds a vote, anything else removes one (a pair cancels). A value with more than half the votes outnumbers everything else combined, so it can never be fully cancelled: it is the survivor.

Trace for 2 2 1 1 1 2 2: votes 1, 2, 1, 0, then 1 becomes the candidate (1), back to 0, then 2 becomes the candidate (1). Candidate: 2.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> readCase(const string& first) {
    if (first == "big") {   // test: 149,999 different numbers, then 150,001 sevens
        vector<int> v;
        for (int i = 0; i < 149999; i++) v.push_back(100 + i);
        for (int i = 0; i < 150001; i++) v.push_back(7);
        return v;
    }
    vector<int> v(stoi(first));
    for (int& x : v) cin >> x;
    return v;
}

int main() {
    string first;
    while (cin >> first) {
        vector<int> v = readCase(first);
        int candidate = 0, votes = 0;
        for (int x : v) {
            if (votes == 0) candidate = x;
            votes += (x == candidate) ? 1 : -1;
        }
        int answer = candidate;
        cout << "majority " << answer << "\n";
    }
    return 0;
}

Input (the small tests, big, 1 2 3):

majority 2
majority 3
majority 9
majority 7
majority 3

Wrong for 1 2 3: voting only guarantees that if a majority exists, it survives. If none exists, something still survives (1 cancels 2, 3 is left).

Fix: count the candidate in a second pass

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> readCase(const string& first) {
    if (first == "big") {   // test: 149,999 different numbers, then 150,001 sevens
        vector<int> v;
        for (int i = 0; i < 149999; i++) v.push_back(100 + i);
        for (int i = 0; i < 150001; i++) v.push_back(7);
        return v;
    }
    vector<int> v(stoi(first));
    for (int& x : v) cin >> x;
    return v;
}

int main() {
    string first;
    while (cin >> first) {
        vector<int> v = readCase(first);
        int candidate = 0, votes = 0;
        for (int x : v) {
            if (votes == 0) candidate = x;
            votes += (x == candidate) ? 1 : -1;
        }
        int count = 0;
        for (int x : v)
            if (x == candidate) count++;
        int answer = (count > (int)v.size() / 2) ? candidate : -1;
        cout << "majority " << answer << "\n";
    }
    return 0;
}

Input (the same, plus 1 1 2 2):

majority 2
majority 3
majority 9
majority 7
majority -1
majority -1

O(n) time (two passes), O(1) extra space. Alternatives: sort and check the middle element (O(n log n)), or an unordered_map of counts (O(n) time, O(n) memory).

Complexity summary

Program Time Extra space
remove duplicates, write index / erase-unique O(n) O(1)
missing number, sum in long long O(n) O(1)
missing number, XOR O(n) O(1)
majority, count every element O(n²) O(1)
majority, sort / hash map O(n log n) / O(n) O(1) / O(n)
majority, Boyer-Moore + check O(n) O(1)

Common mistakes (and the real results)

Mistake What you see Why Fix
unique(v.begin(), v.end()); alone 5: 1 2 3 3 3 unique only moves v.erase(unique(...), v.end())
unique on an unsorted vector repeats remain only adjacent repeats go sort first (if order doesn't matter)
int expected = n * (n + 1) / 2; missing -2147360192 n * (n + 1) overflows (long long)n * (n + 1) / 2, or XOR
(long long)(n * (n + 1)) still wrong the cast comes too late cast n itself
count every element Time Limit Exceeded O(n²) Boyer-Moore voting
print the voting candidate 1 2 3 → 3 someone always survives count it in a second pass

Your turn: the repeated number (solution)

Problem. n + 1 numbers, each from 1..n, and exactly one value appears twice: find it.

The input sum is 1 + ... + n plus the repeated value, so subtract.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        long long sum = 0;
        for (int i = 0; i < n + 1; i++) { int x; cin >> x; sum += x; }
        long long expected = (long long)n * (n + 1) / 2;   // 1 + 2 + ... + n
        cout << "repeated " << sum - expected << "\n";
    }
    return 0;
}

Input 4 / 1 3 4 2 2 / 3 / 3 1 3 2:

repeated 2
repeated 3

A second way: a vector<bool> seen(n + 1), and the first value already seen is the answer (O(n) memory). (If a value may appear more than twice, Floyd's cycle detection solves it in O(1) memory: see episode 23.)

Practice questions (with solutions)

1. Remove duplicates but allow each value at most twice (1 1 1 2 2 2 3 → 1 1 2 2 3). Compare with v[k - 2].

Solution
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        int k = 0;
        for (int i = 0; i < n; i++)
            if (k < 2 || v[i] != v[k - 2]) v[k++] = v[i];   // allow each value twice
        v.resize(k);
        cout << v.size() << ": ";
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Input 7 / 1 1 1 2 2 2 3:

5: 1 1 2 2 3 

2. Two numbers missing from 1..n. The sums give a + b; the sums of squares give a² + b²; then (a − b)² = 2(a² + b²) − (a + b)².

Solution
#include <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        long long sum = 0, sq = 0;
        for (int i = 0; i < n - 2; i++) { long long x; cin >> x; sum += x; sq += x * x; }
        long long S = (long long)n * (n + 1) / 2 - sum;                    // a + b
        long long Q = (long long)n * (n + 1) * (2 * n + 1) / 6 - sq;       // a² + b²
        // (a - b)² = 2Q - S²
        long long D = 0, d2 = 2 * Q - S * S;
        while ((D + 1) * (D + 1) <= d2) D++;
        long long a = (S + D) / 2, b = (S - D) / 2;
        cout << "missing " << b << " and " << a << "\n";
    }
    return 0;
}

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

missing 2 and 4
missing 1 and 5

(The square of n up to about 10⁶ still fits in long long; for very large n use the XOR partition method instead.)

3. Every value appearing more than n / 3 times (at most two such values). Boyer-Moore with two candidates, then verify both.

Solution
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        int c1 = 0, c2 = 1, v1 = 0, v2 = 0;           // two candidates (c1 != c2 at the start)
        for (int x : v) {
            if (x == c1) v1++;
            else if (x == c2) v2++;
            else if (v1 == 0) { c1 = x; v1 = 1; }
            else if (v2 == 0) { c2 = x; v2 = 1; }
            else { v1--; v2--; }                      // three different values cancel
        }
        int k1 = 0, k2 = 0;
        for (int x : v) { if (x == c1) k1++; else if (x == c2) k2++; }
        cout << "more than n/3:";
        if (k1 > n / 3) cout << " " << c1;
        if (k2 > n / 3) cout << " " << c2;
        cout << "\n";
    }
    return 0;
}

Input 8 / 3 1 3 2 1 3 1 2 / 6 / 1 2 3 4 5 6:

more than n/3: 3 1
more than n/3:

Mini project: a vote report

Distinct values (sort + erase-unique on a copy) and the verified majority.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        int candidate = 0, votes = 0;
        for (int x : v) {
            if (votes == 0) candidate = x;
            votes += (x == candidate) ? 1 : -1;
        }
        int count = 0;
        for (int x : v) if (x == candidate) count++;
        vector<int> d = v;
        sort(d.begin(), d.end());
        d.erase(unique(d.begin(), d.end()), d.end());
        cout << "distinct " << d.size() << ", majority ";
        if (count > n / 2) cout << candidate; else cout << "none";
        cout << "\n";
    }
    return 0;
}

Input 7 / 2 2 1 1 1 2 2 / 4 / 1 1 2 2:

distinct 2, majority 2
distinct 2, majority none

Quick quiz

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 4, 4, 7, 7, 9};
    auto it = unique(v.begin(), v.end());
    cout << (it - v.begin()) << " "
         << v.size() << "\n";
    return 0;
}

(A) 3 6 (B) 3 3 (C) 6 6 (D) 6 3

Answer

(A) 3 6. Three values were kept (4 7 9), so the returned iterator is 3 elements in, but unique never changes size().

3 6

Interview questions

  1. What does std::unique do? Moves the first of every run of equal adjacent elements to the front and returns the new logical end; it does not change the size.
  2. What is the erase-unique idiom? v.erase(unique(v.begin(), v.end()), v.end()); (after sorting if needed).
  3. Find the missing number from 1..n. Sum formula in long long, or XOR; O(n), O(1).
  4. Why can n * (n + 1) / 2 be wrong? int overflow for n above about 46,340; cast n to long long first.
  5. Explain Boyer-Moore voting. Cancel pairs of different values; a true majority always survives; O(n), O(1).
  6. Why must the candidate be verified? Without a majority, some value still survives the cancelling.
  7. Majority element with sorting? If a majority exists, it is at index n / 2 after sorting.

Glossary

Term Meaning Example
Sorted Every element ≤ the next 1 1 2 3 3
Duplicate A value already seen the second 1
Iterator A position in a container v.begin()
std::unique Moves away adjacent repeats, returns the new end unique(b, e)
erase(first, last) Removes a range of elements v.erase(it, v.end())
Erase-unique idiom v.erase(unique(...), v.end()) remove duplicates
Write index Where the next kept element goes v[k++] = v[i]
resize(k) Shrinks (or grows) a vector to k elements v.resize(3)
Signed overflow A signed result too big for its type: UB 200000 * 200001 in int
INT_MAX 2,147,483,647 <climits>
Cast Converting a value to another type (long long)n
XOR ^ 1 where bits differ; a ^ a = 0 5 ^ 5 = 0
Majority element Appears more than n / 2 times 2 in 2 2 1 1 1 2 2
Boyer-Moore voting Cancel pairs; the majority survives candidate + votes
Candidate The survivor that still has to be checked 3 for 1 2 3
O(n²) Work grows with the square of n counting each element
Time Limit Exceeded (TLE) The judge stopped a program that ran too long 8 seconds here

Summary

  • std::unique moves, erase cuts: v.erase(unique(v.begin(), v.end()), v.end()). Underneath, a write index plus resize.
  • Missing number: expected sum − actual sum in long long (cast before multiplying), or XOR everything.
  • Majority element: Boyer-Moore voting in one pass, then count the candidate to confirm.

Next episode: Vector questions III: two-sum (brute force vs unordered_map), the maximum subarray sum (Kadane's algorithm, all-negative input), and range sum queries with prefix sums.