Unable to get proper output | Time complexity

Question

Refer below code:

https://code.sololearn.com/cHbY9mfzzl1Q/?ref=app

expected output with current input in code is 9. If last element from input vector (9 here) is removed, expected output is 1.

can anyone please help me with issue in code?

Answer 1

Unfortunately, I couldn't figure out the source of the problem, but I came up with a more primitive approach to tackle that (with a bit of seasoning of course!)

1. In line 55, and 1 to "vecFreq[iCurData ].intFreq" as

objTemp.intFreq = vecFreq[iCurData ].intFreq + 1 ;

which causes to increase the respective data member, by each occurrence of the same value.

2. Replace the "compareFrequency" function with

structFreq compareFrequency( vector<structFreq> &vf )
{
structFreq tmpF;
int lastMaxData = 0;
int lastMaxFreq = 0;
tmpF.intData = 0;
tmpF.intFreq = 0;

for (const structFreq &i : vf) {
cout << "i.intData is " << i.intData << endl;
cout << "i.intFreq is " << i.intFreq << endl << endl;

int currentMaxData = i.intData;
int currentMaxFreq = i.intFreq;

if (currentMaxFreq > lastMaxFreq) {
tmpF.intData = currentMaxData;
tmpF.intFreq = currentMaxFreq;

lastMaxData = currentMaxData;
lastMaxFreq = currentMaxFreq;
}
else if ( (currentMaxFreq == lastMaxFreq) && (currentMaxData > lastMaxData) ) {
tmpF.intData = currentMaxData;

lastMaxData = currentMaxData;
}
}
return tmpF;
}

3. Replace line 74 through 80 with

structFreq result = compareFrequency(vecFreq);
cout<< "Biggest data with High frequency is " << result.intData << ", with " << result.intFreq << " occurence";

Answer 2

Here is my solution.

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

// find out mode of input data...
// If data is 6,1,2,4,5; mode should be 1 as all element are present only once and among them, one is smallest
// If data is 2,3,2,5,1,5,8,9,6,5; mode should be 5.

struct structFreq
{
int intData;
int intFreq;
};

bool compareFrequency(const structFreq &a, const structFreq &b)
{
if(a.intFreq==b.intFreq )
return a.intData < b.intData;
return a.intFreq < b.intFreq;
}

int main()
{
// input for which mode is to be found
vector<int> vecInput {2,6,8,1,9,4,3,5,7,9};

vector<structFreq> vecFreq;
structFreq objTemp;
objTemp.intData = vecInput[0];
objTemp.intFreq = 1;
vecFreq.push_back(objTemp);

//size of input data
int intVecSize = vecInput.size();

//loop through all input data
for(int iCur=1;iCur < intVecSize ;++iCur)
{

int intInput = vecInput[iCur];

//size of data vector
int intDataSize = vecFreq.size();

int intToAddAt = -1;
for(int iCurData=0;iCurData < intDataSize ;++iCurData)
{
if((vecFreq[iCurData ].intData) == intInput )
{
std::cout<<" Before = intInput =>"<<intInput<<" vecFreq[iCurData ].intData =>"<<vecFreq[iCurData ].intData<< "vecFreq[iCurData ].intFreq = "<<vecFreq[iCurData ].intFreq<<std::endl;
//structFreq objTemp;
//objTemp.intData = intInput ;
//objTemp.intFreq = vecFreq[iCurData ].intFreq;
//vecFreq.erase(vecFreq.begin()+iCurData);
//vecFreq.push_back(objTemp);
intToAddAt = 99;
vecFreq[iCurData ].intFreq++;
std::cout<<" After = intInput =>"<<intInput<<" vecFreq[iCurData ].intData =>"<<vecFreq[iCurData ].intData<< "vecFreq[iCurData ].intFreq = "<<vecFreq[iCurData ].intFreq<<std::endl;
break;// break loop of data
}
}

// add if not found
if(intToAddAt==-1)
{
structFreq objTemp;
objTemp

Answer 3

Two mistake are there.
1. Not incrementing freq.
2. comparator in sort method was not working as per your assumption.

Now your task to solve the comparator function.

Answer 4

Ketan Lalcheta np.... to improve time complexity you should avoid unnecessary variale or object creations. also instead of push_back you should use emplace_back.

one more thing is to check complexity of built-in sort with user define sort.

I think you should remove inner for loop of vecFreq check.

I think instead of vector you can use structure array.

Answer 5

Before applying sort it looks like your freq is not incremented for 9.

Here is trace output:
(gdb) p vecFreq
$1 = std::vector of length 9, capacity 16 = {{intData = 2, intFreq = 1}, {intData = 6, intFreq = 1}, {intData = 8, intFreq = 1}, {intData = 1,
intFreq = 1}, {intData = 4, intFreq = 1}, {intData = 3, intFreq = 1}, {intData = 5, intFreq = 1}, {intData = 7, intFreq = 1}, {
intData = 9, intFreq = 1}}
(gdb)

Answer 6

I got it... I was not adding 1 to frequency... now, I updated the code to add one, but still not getting expected output

Answer 7

Solution for your comparator function:
bool compareFrequency(const structFreq &a, const structFreq &b)
{
if(a.intFreq==b.intFreq )
return a.intData < b.intData;
return a.intFreq > b.intFreq;
}

Answer 8

yes , it's working now..thanks everyone for your help...

Actually, this is what I tried to implement for mode calculation of data... my intention was to find out proper solution for this problem in terms of time complexity... Can anyone help me with the same to let me know what solution could be the best for this problem?

Answer 9

new learning for me is emplace_back... thanks for this.. I must use it as I have not pre set size of vector...

Regarding default sort function's complexity, I thought to use map (value, frequency) instead of vector but needed to use user defined sorting only... Any idea what could be done with default sorting for this problem will be of great help. (two criteria to be fulfilled..max frequency and if frequency is max, min data value from same frequency)

And one more point about removal of inner for loop...Do you mean to say that one should use find instead of inner loop?

Answer 10

Ketan Lalcheta once you have done with above checks please share your code with us.

Answer 11

Ketan Lalcheta according to below vector will be the good to use here, but still you can use std::vector::reserve here.
http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-summary.html

For inner loop compare the complexity of user defined loop( i mean code you wrote here) with find algorithm and use accordingly.

Also check the complexity of structure object creation using default and parameterized constructor and use accordingly. Also check for the constructor initializer list.

Please share your findings on complexity on same thread so other can aware about it.