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
- What does
std::uniquedo? 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. - What is the erase-unique idiom?
v.erase(unique(v.begin(), v.end()), v.end());(after sorting if needed). - Find the missing number from 1..n. Sum formula in
long long, or XOR; O(n), O(1). - Why can
n * (n + 1) / 2be wrong?intoverflow for n above about 46,340; castntolong longfirst. - Explain Boyer-Moore voting. Cancel pairs of different values; a true majority always survives; O(n), O(1).
- Why must the candidate be verified? Without a majority, some value still survives the cancelling.
- 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::uniquemoves,erasecuts:v.erase(unique(v.begin(), v.end()), v.end()). Underneath, a write index plusresize.- 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.