Wednesday, April 24, 2013
Leetcode: Divide Two Integers in C++
Divide two integers without using multiplication, division and mod operator.Solution: O(log(a/b))
unsigned int unsigndivide(unsigned int dividend, unsigned int divisor, unsigned int& mod)
{
if(divisor == dividend)
{
mod = 0;
return 1;
}
else if(divisor>dividend)
{
mod = dividend;
return 0;
}
else
{
unsigned int addup = divisor+divisor;
if(dividend>=addup)
{
unsigned int result1 = unsigndivide(dividend, addup, mod);
unsigned int result2 = unsigndivide(mod, divisor, mod);
return result1+result1+result2;
}
else
{
mod = dividend - divisor;
return 1;
}
}
}
int divide(int dividend, int divisor) {
bool flag = false;
if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))
flag = true;
unsigned int abs_dividend=abs(dividend);
unsigned int abs_divisor =abs(divisor);
unsigned int mod =0;
unsigned int result = unsigndivide(abs_dividend, abs_divisor, mod);
if(flag)
return 0-result;
return result;
}
Labels:
Binary Search
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment