i solved the question given below and its giving correct answer, but i need help in getting it done within time limits.
Quest :- http://www.codechef.com/problems/CVOTE
Soln :- http://www.codechef.com/viewsolution/2416258
@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
@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).