How to find the maximum average marks in 2D vector of string?

Question

I have taken the name and marks of each student in 2D vector of string. How can we find the student name having maximum average Marks

I am not able to fetch the Marks of student as it is string in 2d vector. I can do the same using STL Map. But how to do the same using 2D vector of string.

vector<vector<string>>vect {{"James", "70"}, {"Fernando", "40"}, {"Nick", "60"},{"James", "90"},{"Nick", "70"},{"Amit", "50"}};

Expected output is "James : 80"

Welcome to stackoverflow! When asking it's advisable to abstract out the details, at least in the title (i.e. average value in a vector of strings) It's also worth to split the problem into subproblems (e.g. iterate over vector, extract numbers, calculate average) - each of them has an answer also, most people expect questions to contain your inital attempt(s) (in code) — Yuri Feldman, Aug 08 '19 at 05:48
Hi Yuri , Thanks for your suggestion. Can you please provide me a sample code that how to extract the Number from 2D Vector of string. — susjaisw, Aug 08 '19 at 05:52
You want to do this _in place_ without any additional memory, that is with _O(1)_ auxiliary memory requirements? It's possible, but it will be terribly inefficient. — Daniel Langr, Aug 08 '19 at 08:27

score 0 · Answer 1 · answered Aug 08 '19 at 08:39

0

You can do it this way as well

int max = stoi(vect[0][1]);
string name;
for(int i=0;i<vect.size();i++)
    If(max < stoi(vect[i][1]))
    {
        max = stoi(vect[i][1]);
        name.insert(0,vect[i][0]);
    }

Here, name is the person who's scored the maximum average marks

answered Aug 08 '19 at 08:39

Taher Lunawadi

51
2
8

2

Where do you calculate the average? – Daniel Langr Aug 08 '19 at 08:41
Where I've assigned `max = stoi(vect[i][1]);`, there you can do it as `max = stoi(vect[i][1])/vect[i].size();` – Taher Lunawadi Aug 08 '19 at 08:44
2

`vect[i].size()` is always 2. What if some student has more than 2 scores? Where do you sum his/her scores? – Daniel Langr Aug 08 '19 at 08:45
I kinda missed to add that initialize `max` as `max = stoi(vevt[0][1])/vect[0].size();` – Taher Lunawadi Aug 08 '19 at 08:47
You can add n number of marks in the vector by using `vect[i].push_back()` method – Taher Lunawadi Aug 08 '19 at 08:49
Later on when you find the average, declare a variable sum and in a loop sum up all the marks you have entered – Taher Lunawadi Aug 08 '19 at 08:50
You can sum up in this way `for(int j=1;i – Taher Lunawadi Aug 08 '19 at 08:52
Can you please provide the complete and working code? It doesn't work for me: https://wandbox.org/permlink/wwvn1IxY9JFE8K2v. You can modify this online example to make it correct. – Daniel Langr Aug 08 '19 at 08:54
Here's the link to the working code https://wandbox.org/permlink/gLXiDKx2JNg7o9JG . – Taher Lunawadi Aug 08 '19 at 14:24
Working? It generates a runtime error. Have you tried to verify the output? – Daniel Langr Aug 08 '19 at 14:28
I have checked the code but there's some problem with `std::stoi()` it seems, I am trying to resolve the error, I will get back to you as soon as I am done – Taher Lunawadi Aug 08 '19 at 14:39

Daniel Langr · Answer 2 · 2019-08-08T09:02:34.880

If you want to do the calculation in place, that is with O(1) additional memory requirements, you can use the following approach:

Iterate over all the records.
Find out if the actual name hasn't been already processed before (by comparing the name with all the records having lower indexes).
If not, find all the records having the same name starting from the actual one while summing up the scores and their count.
Calculate the average (sum / count).
If the average is higher the up-to-now maximum, update this maximum to the actual one.

Hope you can write the code by yourself ;-)

Note that this approach does not modify the input vector. If you can to that, a better approach would be to sort it first by name and then perform one linear pass by its elements, as suggested by @mahbubcseju.

mahbubcseju · Answer 3 · 2019-08-08T15:13:37.950

Firstly sort the vector by using the name as key . After that all the same persons will be besides each others. For Example:

  vector<vector<string>>vect {{"James", "70"}, {"Fernando", "40"}, {"Nick", "60"},{"James", "90"},{"Nick", "70"},{"Amit", "50"}};

   sort(vect.begin(),vect.end());
   for(int i=0;i<vect.size();i++){
      cout<<vect[i][0]<<" "<<vect[i][1]<<endl;
   }

This will output like following:

Amit 50
Fernando 40
James 70
James 90
Nick 60
Nick 70

After that iterate through the row vector by the following way and calculate the average:

   int ma=-1;
   string maxPerson="";
   int counter=0;
   int cumSum=0;
   for(int i=0;i<vect.size();i++){

   if(i>0&&vect[i][0]!=vect[i-1][0]){
       int avg=(cumSum/counter);
       if(avg>ma){
          ma=avg;
          maxPerson=vect[i-1][0];
       }

      counter=1;
      cumSum=stringTonumber(vect[i][1]);
   }
   else {
       counter++;
       cumSum+=stringTonumber(vect[i][1]);
   }

} int avg=(cumSum/counter); if(avg>ma){ ma=avg; maxPerson=vect[vect.size()-1][0]; }

You can declare ma and avg variable as double to calculate the real average if need. Cz sometimes result can be 90.5 but int will not consider .5.

Whole code:

#include <bits/stdc++.h>

#define LEN 150
using namespace std;
int stringTonumber(string x)
{
    int num = 0;
    for (int i = 0; i < x.size(); i++) {
        num = num * 10 + x[i] - '0';
    }
    return num;
}
int main()
{
    vector<vector<string> > vect{ { "James", "70" }, { "Fernando", "90" }, { "Fernando", "80" }, { "Fernando", "100" }, { "Nick", "60" }, { "James", "80" }, { "Nick", "70" }, { "Amit", "50" } };

    sort(vect.begin(), vect.end());
    for (int i = 0; i < vect.size(); i++) {
        cout << vect[i][0] << " " << vect[i][1] << endl;
    }
    int ma = -1;
    string maxPerson = "";
    int counter = 0;
    int cumSum = 0;
    for (int i = 0; i < vect.size(); i++) {

        if (i > 0 && vect[i][0] != vect[i - 1][0]) {
            int avg = (cumSum / counter);
            if (avg > ma) {
                ma = avg;
                maxPerson = vect[i - 1][0];
            }

            counter = 1;
            cumSum = stringTonumber(vect[i][1]);
        }
        else {
            counter++;
            cumSum += stringTonumber(vect[i][1]);
        }
    }
    int avg = (cumSum / counter);
    if (avg > ma) {
        ma = avg;
        maxPerson = vect[vect.size() - 1][0];
    }
    cout << maxPerson << " " << ma << endl;

    return 0;
}

Please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) (Would be somewhat fine with a remark like "replace this with a proper list of single includes", although even then, people might take it over) — Aziuth, Aug 08 '19 at 10:03
Also, `std::stoi` is more elegant than defining your own `StringTonumber` (alternatively, more archaic, `std::atoi` with a char array as argument) — Aziuth, Aug 08 '19 at 10:28
@mahbubcseju : This Approaches fail for the input : "James", "70"}, {"Fernando", "90"},{"Fernando", "80"},{"Fernando", "100"}, {"Nick", "60"},{"James", "80"},{"Nick", "70"},{"Amit", "50"}}; Expected Output : Fernando 90 Your output : Fernando 100 — susjaisw, Aug 08 '19 at 14:22

Aziuth · Answer 4 · 2019-08-08T10:39:18.183

My approach: Use a map Student -> Vector of Marks, fill it, then average it.

map<string, vector<double> > marks;

for(const vector<string>& entry : vect)
{
    string name = entry[0];
    int mark = stod(entry[1]);
    marks[name].push_back(mark);
}

Now you have a map filled with a vector of marks for each student, easy to handle. If you want the averages, go like:

string best_student = "nobody";
double best_average = 0.;

for(auto const& entry : marks)
{
    const string& name = entry.first;
    const vector<double>& student_marks = entry.second;
    double average = accumulate(student_marks.begin(), student_marks.end(), 0) / student_marks.size();

    cout << "The student " << name << " has an average mark of " << average << endl;

    if(average > best_average)
    {
        best_average = average;
        best_student = name;
    }
}

cout << endl;
cout << "The student with the highest average mark is " << best_student << " with " << best_average << endl;

(Note that you need to #include<numeric> for std::accumulate, and that I used for each, thus you need at least C++11.)

Might not be the most time optimized approach, but works nicely and is quite readable as far as I see it.

I implemented this here: http://cpp.sh/6lijg

(I did some assumptions that one might check (/handle by something like throwing an exception if not met or printing some message): 1. The original vector is always correctly filled, that is every subvector has length 2; 2. the original vector always has at least one entry; 3. marks are non-negative and there is a student with a non-zero mark - else the initializations of best_student and best_mark are wrong.)

How to find the maximum average marks in 2D vector of string?

4 Answers4