SKD
BAN USERComplexity : O(logn) where n= max(number of bits in divisor, number of bits of dividend)
//division of two integers without using '/' symbol
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
using namespace std;
int division(int,int);
int wrapper_division(int,int);
int divisor, dividend, _remainder;
int wrapper_division(int t_dividend, int t_divisor)
{
int quotient= division(abs(t_dividend), abs(t_divisor));
if(_remainder!=0)
{
if(t_dividend < 0 && t_divisor > 0)
{
_remainder++;
return -(quotient+1);
}
else if(t_dividend > 0 && t_divisor < 0)
{
_remainder= -(abs(t_divisor)-_remainder);
return -(quotient+1);
}
else if(t_dividend < 0 && t_divisor < 0)
{
_remainder= -_remainder;
return quotient;
}
else
return quotient;
}
if(t_divisor<0 || t_dividend<0)
return -quotient;
return quotient;
}
int division(int t_dividend, int t_divisor)
{
int quotient = 1;
if(t_divisor==0)
{
cout<<"DIVISION BY ZERO NOT POSSIBLE"<<endl;
exit(1);
}
if (t_divisor==t_dividend)
{
_remainder=0;
return 1;
}
else if(t_dividend < t_divisor)
{
_remainder = t_dividend;
return 0;
}
while(t_divisor <= t_dividend)
{
t_divisor <<= 1;
quotient <<= 1;
}
t_divisor >>= 1;
quotient >>= 1;
quotient = quotient + division( abs(t_dividend - t_divisor), abs(divisor));
return quotient;
}
//Unit test
int main(void)
{
dividend= 10, divisor= 3;
int quotient= wrapper_division(dividend, divisor);
assert(quotient==3 && _remainder ==1);
cout<<"Test 1 passed..."<<endl;
cout<<"quotient: "<<quotient<<" _remainder: "<<_remainder<<endl;
dividend= -10, divisor= 3;
quotient= wrapper_division(dividend, divisor);
assert(quotient==-4 && _remainder ==2);
cout<<"Test 2 passed..."<<endl;
cout<<"quotient: "<<quotient<<" _remainder: "<<_remainder<<endl;
dividend= 10, divisor= -3;
quotient= wrapper_division(dividend, divisor);
assert(quotient==-4 && _remainder == -2);
cout<<"Test 3 passed..."<<endl;
cout<<"quotient: "<<quotient<<" _remainder: "<<_remainder<<endl;
dividend= -10, divisor= -3;
quotient= wrapper_division(dividend, divisor);
assert(quotient==3 && _remainder == -1);
cout<<"Test 4 passed..."<<endl;
cout<<"quotient: "<<quotient<<" _remainder: "<<_remainder<<endl;
}
It would be better if you mention that we need to sort the above bank cities with respect to lower banks.
- SKD December 26, 2014By the way, can you please tell how did you come up with the solution?