Abhay
BAN USER
Comments (4)
Reputation 85
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
6
of 8 vote
Since 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=1e4;
int factor=1;
if( a*b < 0 ) /*for handling negative cases*/
factor=1;
a=abs(a);
b=abs(b);
do
{
float mid=low +(highlow)/2;
float product=b*mid;
if(absolute (product  a) < tolerence)
return mid*factor;
if(product < a)
low = mid;
else
high=mid;
}while(absolute(highlow) > 1e3);
return low*factor;
}

Abhay
December 14, 2014 Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 5 vote
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>=n1)
return true;
if(maxInd<=i)
return false;
}
u can test your solution over here https://oj.leetcode.com/problems/jumpgame/
 Abhay December 02, 2014Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
Lol
 Abhay January 04, 2015