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

int divide(int numerator, int denominator) {

...

}

**Solution:**Let’s start with an example. In this case,

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:

int answer, curValue, i;

for (i=0, answer=0, curValue=numerator;
i < numerator; i+=denominator) {

curValue -= denominator;

answer++;

answer++;

}

// round up if necessary

if ( curValue + curvalue <= denominator) answer++;

if ( curValue + curvalue <= denominator) answer++;

return 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) {

int answer, curValue, i;

//check for 0 denominator

if (denominator == 0) return ERROR_VALUE;

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;

answer++;

i+=denominator;

} else {

//one is negative

curValue+=denominator;

answer--;

i-= denominator;

}

if (numberator >= 0 && denominator > 0) {

curValue -= denominator;

answer++;

i+=denominator;

} else {

//one is negative

curValue+=denominator;

answer--;

i-= denominator;

}

}

// round up if needed

if (curValue + curvalue <= denominator) answer++;

if (curValue + curvalue <= denominator) answer++;

return answer;

}

This is an example of a
problem which starts out simple, and gets much more complicated. It’s good to do some examples now with
varying positive and negative numerators and where you round down and up. There’s actually still a bug in this
solution, but I’ll leave it to you to discover it.

/*Please let me know if
you know alternate solutions or find bugs other than the one left in
there. Thank you. Noah */

## No comments:

## Post a Comment