07. Arrays and vector — Homework Solutions

The answer .cpp files are in exercises/07/homework/solutions/.

Open this page after trying on your own. Compare your line of reasoning with the How to think about it section, not the code line by line: two pieces of code with different shapes can both be correct, and what is worth copying is how to get there. The Tests section of each problem holds inputs and outputs that have been checked — run your own answer with those inputs before considering yourself done.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/07/homework/solutions/01-statistik.cpp
./jawab

Problem 1 — Simple statistics

Problem. Print the smallest value, the largest value, and the sum of n numbers.

How to think about it. All three answers can be obtained in one pass. The initial values of kecil ("smallest") and besar ("largest") are taken from a[0], not from a guessed number such as 0 or 1000000; that way negative data or very large data is still handled.

The sum accumulator is a long long: 100,000 numbers each up to 10⁹ add up to 10¹⁴.

Walkthrough.

int kecil = a[0], besar = a[0];
long long total = 0;

for (int i = 0; i < n; i++) {
    if (a[i] < kecil) kecil = a[i];
    if (a[i] > besar) besar = a[i];
    total += a[i];
}

cout << kecil << "\n" << besar << "\n" << total << "\n";

Tests.

The last two rows are the edge cases that most often break an answer: an array with a single element (its smallest and largest values are the same), and data that is entirely negative (the initial value of besar must be a[0], not 0).

Common mistakes.

• Starting with besar = 0. For data that is all negative, the answer becomes 0.
• Reading the data into an array but forgetting that its indices are 0 through n - 1.

Problem 2 — Reversing the order

Problem. Print the array's contents from the back, with no trailing space.

How to think about it. There is no need to actually reverse the array's contents; it is enough to traverse it backwards from n - 1 to 0. The spacing is handled as in Chapter 05: print a space before every number except the first one printed.

Walkthrough.

for (int i = n - 1; i >= 0; i--) {
    if (i < n - 1) cout << " ";
    cout << a[i];
}
cout << "\n";

Tests.

The n = 1 case tests the "no space at the end of the line" rule: the output must be a single number, with no space after it. The safest way is to print a space before every number except the first.

Common mistakes.

• Writing for (int i = n; i >= 0; i--), which reads a[n] — outside the data.
• Swapping the array's contents with a full loop (i from 0 to n), which actually restores the original order because every pair is swapped twice. If you do want to swap, the limit is i < n / 2.

Problem 3 — Searching for a value

Problem. Print the index of the first occurrence, or -1.

How to think about it. The linear search pattern: set posisi = -1 (posisi = "position") as the answer for when nothing is found, traverse from the front, and break on the first match. That break is what makes the answer the first index, not the last.

Walkthrough.

int posisi = -1;
for (int i = 0; i < n; i++) {
    if (a[i] == target) { posisi = i; break; }
}
cout << posisi << "\n";

Tests.

The first row is the core of the problem: the number 1 appears twice, and what is asked for is the smallest index. That is why the loop must break as soon as it finds a match — without break, the answer becomes the last occurrence.

Common mistakes.

• Forgetting break, so the index of the last occurrence is printed.
• Printing inside the loop, so a target that appears three times produces three lines of output.

Problem 4 — Sum of each row

Problem. Read a b × k matrix and print the sum of each of its rows.

How to think about it. The key is where the accumulator lives: jumlah ("sum") must be recreated (with value 0) inside the row loop, not outside it. If it is placed outside, the sum piles up from row to row.

Walkthrough.

for (int i = 0; i < b; i++) {
    long long jumlah = 0;
    for (int j = 0; j < k; j++) jumlah += grid[i][j];
    cout << jumlah << "\n";
}

Tests.

Note the reading order: b and k first, then b × k numbers read row by row. cin >> does not care about line breaks, so the layout of the input may differ — but the order of the numbers may not.

Common mistakes.

• Placing long long jumlah = 0; before the outer loop.
• Mixing up the row and column indices (grid[j][i]), which only shows up when the number of rows and columns differ.

Challenge — Sieve of Eratosthenes

Problem. Count the prime numbers up to 10⁶ in under one second.

How to think about it. Reverse the way of thinking from the Chapter 06 problem: instead of asking "is this number prime?" one at a time, mark all multiples of each prime number found at once.

Two details make it fast and correct:

• The outer loop only needs to go up to i * i <= n. Any composite number must have a factor that does not exceed the square root of n, so above that nothing more needs to be crossed out.
• The inner loop starts from i * i, not 2 * i. The smaller multiples (2i, 3i, …) have already been crossed out by smaller prime numbers.

Write (long long)i * i <= n so that the multiplication does not overflow when i approaches the square root of the int limit.

Walkthrough.

coret[0] = true;
if (n >= 1) coret[1] = true;

for (int i = 2; (long long)i * i <= n; i++) {
    if (!coret[i]) {
        for (int j = i * i; j <= n; j += i) coret[j] = true;
    }
}

int banyak = 0;
for (int i = 2; i <= n; i++) if (!coret[i]) banyak++;
cout << banyak << "\n";

Check: n = 1000000 gives 78498, n = 2 gives 1, n = 1 gives 0.

Tests.

The last row also tests speed. Checking each number one at a time with the square-root method takes about 67.7 million steps, whereas the sieve takes only a few million — measured, 0.108 seconds versus 0.001 seconds, about seventy times faster.

Common mistakes.

• Placing the array bool coret[1000001] inside main. An array that large on the stack makes the program crash; declare it as a global variable.
• Forgetting to cross out 0 and 1, so the count is two too high.
• Using an inner loop that starts from 2 * i. The result is still correct, just slower.

OSN-style exercises — walkthrough

The answer files are in exercises/07/osn/solutions/.

Problem 1 — Score Mode

How to think about it. The direct approach — for each value, count how many are equal to it — takes N² = 4 × 10¹⁰ comparisons. Impossible.

The hint is in the constraints: the values are only 1 to 1000, far fewer than the 200,000 data items. So what you build is not an array of the data but a counting array of length 1001. Each number read adds one to its own box, and all the data only needs to be read once.

The condition "if tied, choose the smallest" needs no extra code: if the maximum search runs from small indices to large and uses > (not >=), the smallest value that reaches the highest frequency will never be displaced.

Walkthrough.

const int BATAS = 1000;

int n;
cin >> n;

int cacah[BATAS + 1] = {0};
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cacah[x]++;
}

int nilai = 1;
for (int v = 1; v <= BATAS; v++) {
    if (cacah[v] > cacah[nilai]) nilai = v;
}

cout << nilai << " " << cacah[nilai] << "\n";

The data itself is never stored. This is a pattern that comes up often: if only a summary is asked for, the raw data does not need to be held in memory.

Tests.

Common mistakes.

• Making the array cacah[1000], so cacah[1000] is out of bounds. An array indexed by value always has size maximum + 1.
• Using >= when searching for the maximum, so the largest value wins on a tie instead.
• Storing all the data in an array int a[200000] and then checking it pairwise. Correct, but too slow.

Problem 2 — Smallest Difference

How to think about it. Checking all pairs takes N² / 2 = 2 × 10¹⁰ comparisons — too many.

The key is one sentence: after sorting, the pair with the smallest difference must be adjacent. The reason: if two numbers are not adjacent, then there is another number between them, and that number must be closer to one of the two. So it is enough to sort and then check the N − 1 adjacent pairs.

The cost becomes N log N for the sort plus N for the check.

Walkthrough.

vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

sort(a.begin(), a.end());

long long terkecil = a[1] - a[0];
for (int i = 2; i < n; i++) {
    long long selisih = a[i] - a[i - 1];
    if (selisih < terkecil) terkecil = selisih;
}

cout << terkecil << "\n";

Because the data is already sorted in ascending order, a[i] - a[i-1] is always non-negative — no absolute value is needed. The accumulator's initial value is the difference of the first pair, not a made-up large number: the problem guarantees N ≥ 2, so that pair always exists.

Tests.

The second row checks duplicate data, the third row checks the type: the difference is 2 × 10¹⁸, which still fits in a long long but is far beyond an int.

Common mistakes.

• Using int for the data or for the difference.
• Filling the initial accumulator with a number like 1000000000, which is smaller than the largest possible difference, so the answer is wrong on large data.
• Forgetting to sort, then checking adjacent pairs in the original order.

Problem 3 — Largest Row and Column

How to think about it. There is no need to store the whole table. When a number is read, it is already known to belong to row i and column j, so it can be added straight away to two accumulators: jumlahBaris[i] ("row sum") and jumlahKolom[j] ("column sum"). A single read is enough for both.

The size of the sums needs checking: 500 numbers of value 10⁶ add up to 5 × 10⁸, which still fits in an int, but long long removes any doubt at no meaningful cost.

Row and column numbers are printed starting from 1, whereas array indices start from 0 — that is why one is added to the result at the end.

Walkthrough.

vector<long long> jumlahBaris(r, 0), jumlahKolom(c, 0);

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
        int x;
        cin >> x;
        jumlahBaris[i] += x;
        jumlahKolom[j] += x;
    }
}

int baris = 0;
for (int i = 1; i < r; i++) {
    if (jumlahBaris[i] > jumlahBaris[baris]) baris = i;
}

int kolom = 0;
for (int j = 1; j < c; j++) {
    if (jumlahKolom[j] > jumlahKolom[kolom]) kolom = j;
}

cout << baris + 1 << " " << kolom + 1 << "\n";

Tests.

Common mistakes.

• Printing the array index as is, so the answer is one too small.
• Setting up vector<long long> jumlahKolom(r) — its length must be c, not r. This mistake is invisible on square tables.
• Using >= when searching for the maximum, so the largest number wins.

If you are still stuck

• The program crashes on large data → Chapter 07, the warnings about out-of-bounds indices and local arrays that are too large.
• Wrong answers only for negative data → Chapter 07, the section Basic patterns on arrays (initial value a[0], not 0).
• A loop over a vector behaves nonsensically → Chapter 07, the warning about v.size() being unsigned.

Before moving on to Part 2, make sure you can write from memory: reading n numbers into an array, finding the largest and smallest values, and sorting with sort.