help for [time limit exceeded ]

general
, ,
1

i solved the question given below and its giving correct answer, but i need help in getting it done within time limits.
Quest :- CVOTE Problem - CodeChef
Soln :- CodeChef: Practical coding for everyone

2

@codeanindya : This is the time consuming block :

for(int i=0;i<M;i++)

{

for(int j=0;j<N;j++)

{

if(vote[i].equals(names[j]))

{

arr[j]++;

}

}

}

It makes the time complexity of the algorithm O(M*N) .

You should do binary search in “names” array for “vote[i]” . One name will only occur once and you need to do arr[index]++ for only index found by binary search .

This will make the complexity of the snippet as O(Mlog(N)) and complexity of total algorithm as O(Mlog(N) + N ) .

1 Like
3

@vineetpaliwal : for performing binary search we’ll first have to sort the string array and then call the binary search function. would that not give a Time-complexity only a little less than here.
and also the space-complexity (memory) will increase.

please explain this a little further. and if it doesn’t bothers you to re-right this snippet, please help me with that also (please paste the code here or on pastebin and give me the link).