Abhay
BAN USERSince interviewer has constraint of not using division operator and hinted you to use binary search
we can use multiplication and then apply binary search
the Idea is
suppose a/b=c
=> a=b*c
now we need to apply binary search on c
followig c code will do the work
since abs function does not work for float I have implemented my own
float absolute(float a)
{
return a>0 ? a:-a;
}
float divide(int a,int b)
{
float high=INT_MAX,low=0,tolerence=1e-4;
int factor=1;
if( a*b < 0 ) /*for handling negative cases*/
factor=-1;
a=abs(a);
b=abs(b);
do
{
float mid=low +(high-low)/2;
float product=b*mid;
if(absolute (product - a) < tolerence)
return mid*factor;
if(product < a)
low = mid;
else
high=mid;
}while(absolute(high-low) > 1e-3);
return low*factor;
}
Agorithm:
for each element determine the maximum index you may jump
maxInd=0;
for(i=0;i<n;i++)
{
if(maxInd<a[i]+i)
maxInd = a[i]+i;
if(maxInd>=n-1)
return true;
if(maxInd<=i)
return false;
}
u can test your solution over here https://oj.leetcode.com/problems/jump-game/
- Abhay December 02, 2014
Lol
- Abhay January 04, 2015