## How to

When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!

## Tuesday, February 21, 2012

### Implement division without using the division or multiplication operation

Problem: Implement division without using the division or multiplication operation.  Round to the nearest whole number

int divide(int numerator, int denominator) {
...

}

Numerator= 108
Denominator = 10

We know that the answer to this is 10.8, which rounds up to 11.  But, let’s think about how we got that.  We know that 10 can be multiplied by 10 to get 100.  This is equivalent to adding 10, ten times.

Similarly, we can subtract 10, ten times from 100 to get zero.
This starts to intuit an algorithm, where we see how many times we can subtract and that is most of the answer.

But, how do we deal with what is left over?  In this case it is 8.  We’re supposed to round up or down, so we can compare 8 to 10.  We’re not allowed to divide, but we are allowed to add an compare.  So, we can double 8 by adding it to itself.  If the result is greater than 10, we round up.

Putting this into code, we get:

for (i=0, answer=0, curValue=numerator; i < numerator; i+=denominator) {
curValue -= denominator;
}
// round up if necessary
if ( curValue + curvalue <= denominator) answer++;
}

This is almost right, but it has at least problem.   Can you see it?  If not, try a negative number example.

What do we do if we get a negative number?  In this case, our algorithm fails as one number will go up or down indefinitely.

To solve this, we need to use some if statements to make sure that we are always iterating in the right direction.  We also can’t divide by zero and need to check that case too.   We can solve this with three if statements a shown:

int divide(int numerator, int denominator) {

//check for 0 denominator
if (denominator == 0) return ERROR_VALUE;
for (i=0, answer=0, curValue=numerator; (numerator > 0 && i < numerator) || (numerator < 0 && i > numerator);) {
//if both numerator and denominator are positive or negative:
if (numberator >= 0 && denominator > 0) {
curValue -= denominator;
i+=denominator;
} else {
//one is negative
curValue+=denominator;
i-= denominator;
}
}
// round up if needed
if (curValue + curvalue <= denominator) answer++;