Improvement in Attic crossing

I completed the problem in 3.42 sec! but is there any way to improve it? i mean algorithm wise?
I didn’t follow any algorithm in the below code. Its just plain get-the-output code. My code(In c++) is,

#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int count=0,i,j,cur_dist=0, req_dist=0;
string str;
cin>>str;
for(i=0;i< str.length();i++)
{
if(str[i]==’.’)
{
req_dist++;
}
else
{
if(req_dist> cur_dist)
{
cur_dist=req_dist;
count++;
}
req_dist=0;
}
}
cout<< count;
}
return 0;
}

Hi, arvindkr

when we have to process every element then there is not any algorithm better then O(n) since your solution has linear complexity. but simple thing that you can do is to find the string length once rather than computing every time with loop. and one thing about algo is that if the cur_dist is more than the remaining string length then why to loop it up to end just break the loop.

means condition should be i < str.length() && cur_length < str.length()-i

but it also depend on test cases if length of string is about 10^9 or 10^8 in 1 sec then we should use it and also cur_dist in test cases should be around 10^7 otherwise no matter.

well these are very easy question and state forward so there is nothing like optimization when we go through algo and DS then this term took place.

but it is good practice to find optimized method i.e you are doing :slight_smile: