Problem overview
Version 4 prints the top k brands by rating. The starter data has two parallel vectors, brands and ratings, where ratings[i] belongs to brands[i], and int k = 3;. Each output line has the form rank. Brand (rating), starting at rank 1. When two brands have the same rating, the one listed first ranks higher. The statement promises that k is never larger than the number of brands.
With ratings 4, 5, 3, 5 and 4, the program prints:
1. MegaCorp (5)
2. NeoByte (5)
3. TechPro (4)
The previous version found the single best brand with a loop. This version finds it k times.
Approach: search, mark, search again
You don't need to sort. Find the best brand, mark it as taken, then search again among the brands that aren't taken. The second search finds the second best, the third search the third best, and so on until k brands have been chosen.
The marks live in a vector<bool> named used, with one flag per brand. The program doesn't print inside the search. It builds each finished line as a string and stores it in a vector<string> called lines, and prints them all at the end.
The search uses a strict comparison. A brand replaces the current best only when its rating is strictly higher. That means that when ratings tie, the brand found first, the one listed earlier, stays on top, which is the rule from the statement.
Why not sort?
Sorting ratings would reorder the numbers but leave brands where it is, so every rating would end up next to the wrong name. A correct sort would have to move both vectors together, and it would also need a way to keep equal ratings in their listed order. The repeated search avoids both problems: the data never moves, and the strict comparison settles ties by itself. The cost is speed, which matters little for five brands.
Step by step
- Create
usedasvector<bool> used(ratings.size(), false): onefalseper rating, meaning that nothing is taken yet. - Create an empty
vector<string> lines. Lines arrive one per round, so it starts empty. - Write the outer loop with
rankfrom 1 up to and includingk. The counter does two jobs: it counts the rounds, and it is the number printed in front of the brand. - Start each round with
int bestIndex = -1;, which means no brand is found yet. Every round restarts the search. - Write the inner loop over every position of
ratings. - Skip taken brands: an
if (!used[i])lets only the brands that haven't won yet be candidates. - Compare: a second
ifis true whenbestIndex == -1or whenratings[i]is strictly higher thanratings[bestIndex]. - Remember the brand: set
bestIndex = i. - Mark the winner after the inner loop:
used[bestIndex] = true, so the next round skips it. - Build the line and add it with
push_back: the rank,". ", the brand's name," (", the rating and")". - Print every line with a final loop over
lines.
The solution in C++
vector<string> brands = {"TechPro", "MegaCorp", "Quantum", "NeoByte", "Zenith"};
vector<int> ratings = {4, 5, 3, 5, 4};
int k = 3;
vector<bool> used(ratings.size(), false);
vector<string> lines;
for (int rank = 1; rank <= k; rank++) {
int bestIndex = -1;
for (int i = 0; i < (int)ratings.size(); i++) {
if (!used[i]) {
if (bestIndex == -1 || ratings[i] > ratings[bestIndex]) {
bestIndex = i;
}
}
}
used[bestIndex] = true;
lines.push_back(to_string(rank) + ". " + brands[bestIndex] + " (" + to_string(ratings[bestIndex]) + ")");
}
for (int i = 0; i < (int)lines.size(); i++) cout << lines[i] << endl;
Building the text
C++ can't join a number to text with +: 1 + ". " doesn't produce the text 1. . Each number goes through to_string first. After that, to_string(rank) + ". " + brands[bestIndex] is a string added to a string literal, and the rest of the line follows the same pattern. Because the first operand is already a string, every + after it works.
Here is how the rounds go on the starter data:
| rank | candidates | winner | why |
|---|---|---|---|
| 1 | all five | MegaCorp (5) | NeoByte also has 5 but comes later |
| 2 | all but MegaCorp | NeoByte (5) | the only 5 left |
| 3 | TechPro (4), Quantum (3), Zenith (4) | TechPro (4) | ties with Zenith, listed first |
The program stores bestIndex, a position, instead of the best rating. A position leads to both the name and the rating, because the two vectors share their indexes, and it is also what used needs to mark the brand as taken.
Complexity
Each of the k rounds scans all n brands, so the time is O(k × n). With k close to n, that is about n squared. The extra space is O(n) for used, plus O(k) for lines.
Edge cases and common mistakes
- Ties. Using
>=instead of>would let the later brand win every tie, and the output would start with NeoByte. - Forgetting
used[bestIndex] = true. Every round would then return MegaCorp. kequal to the number of brands. Withk = 5the output has five lines: MegaCorp, NeoByte, TechPro, Zenith (4) and Quantum (3). Everybody ranks once.k = 1. The output is the first line only:1. MegaCorp (5).- A
klarger than the number of brands. The statement rules this out. This version has no safeguard: a round with nobody left would leavebestIndexat -1 and the program would useused[-1], which is undefined behaviour. - Starting rank at 0. The lines would be numbered 0, 1, 2.
Testing
Run the starter data for the three lines above. Try k = 1 for one line and k = 5 for all five brands in rank order.
