Binary search on answer c++


#1

bool isvalid(vector arr,int mid)
{
for(int i=0;i<=mid;i++)
{
char k=arr[0][i];
for(auto s:arr)
{
if(s[i]!=k)
return false;
}
}
return true;
}
string Solution::longestCommonPrefix(vector &A) {
int start=0,end,ml=INT_MAX;
for(auto s:A)
if(s.length()<ml)
ml=s.length();
end=ml;int res=-1;
while(start<=end)
{
int mid=end+(start-end)/2;
if(isvalid(A,mid))
{
res=mid;
start=mid+1;
}
else
end=mid-1;

}
return A[0].substr(0,res+1);

}