# Algorithm help: minimum distance to multiple

Garrett Rowe

Ranch Hand

Posts: 1296

posted 3 years ago

I'm not sure if this belongs in this forum, but it is more an algorithm question than a programming, or language specific question.

Given a function that takes 2 integer parameters, f(a, b), it should return a number representing how much you have to add to a to make it a multiple of b.

So:

f(1, 2) = 1

f(2, 2) = 0

f(1, 3) = 2

f(4, 3) = 2

f(5, 3) = 1

f(6, 3) = 0

What I have seems correct, but overly complicated:

f(a, b) = (b - (a % b)) % b

Is there a~~better~~ cleaner way?

Given a function that takes 2 integer parameters, f(a, b), it should return a number representing how much you have to add to a to make it a multiple of b.

So:

f(1, 2) = 1

f(2, 2) = 0

f(1, 3) = 2

f(4, 3) = 2

f(5, 3) = 1

f(6, 3) = 0

What I have seems correct, but overly complicated:

f(a, b) = (b - (a % b)) % b

Is there a

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Ryan McGuire

Ranch Hand

Posts: 1078

4

posted 3 years ago

I would call Garrett's solution "righter" because you "have to" add 0 to 6 to make it a multiple of 3, but you don't "have to" add 3. I interpreted the original problem statement to say we're looking for the minimum non-negative integer that satisfies the condition.

How about...

b - 1 - ((a -1 ) % b)

That formula replaces the second MOD operation from Garrett's version with an extra +1 and -1. However, it has a minor fail when a=0, in which case a-1 == -1 and -1 % b == -1. We could modify it a bit so that the left side of the % doesn't go negative for non-negative values of a:

(b-1) - ((a + (b-1)) % b)

That looks like a total of four addition and subtractions. However, you could cache the value for b-1:

c = b-1

answer = c - ((a + c) % b)

So... three addition/subtractions and one MOD.

Paul Clapham wrote:

Edit: If a is already a multiple of b then my formula returns b and your formula returns 0. You might think yours is "righter" than mine in that case but both satisfy the stated requirements.

I would call Garrett's solution "righter" because you "have to" add 0 to 6 to make it a multiple of 3, but you don't "have to" add 3. I interpreted the original problem statement to say we're looking for the minimum non-negative integer that satisfies the condition.

How about...

b - 1 - ((a -1 ) % b)

That formula replaces the second MOD operation from Garrett's version with an extra +1 and -1. However, it has a minor fail when a=0, in which case a-1 == -1 and -1 % b == -1. We could modify it a bit so that the left side of the % doesn't go negative for non-negative values of a:

(b-1) - ((a + (b-1)) % b)

That looks like a total of four addition and subtractions. However, you could cache the value for b-1:

c = b-1

answer = c - ((a + c) % b)

So... three addition/subtractions and one MOD.

Ryan McGuire

Ranch Hand

Posts: 1078

4

vishal saha

Ranch Hand

Posts: 30

Ryan McGuire

Ranch Hand

Posts: 1078

4

posted 3 years ago

This assumes that b^2 > a.

For f(14, 3), b^2 - a in this case would be -5. In Java, -5 % 3 = -2. If I understand the requirements correctly, the answer should be 1.

vishal saha wrote:result = (b^2 - a)

result = result % b

clean ? :-)

This assumes that b^2 > a.

For f(14, 3), b^2 - a in this case would be -5. In Java, -5 % 3 = -2. If I understand the requirements correctly, the answer should be 1.

vishal saha

Ranch Hand

Posts: 30

posted 3 years ago

With two variables you could save yourself a subtraction, viz:I suspect also that comparison with 0 is quicker, but it might all be offset by having an extra variable.

Ain't optimization fun?

Winston

Ryan McGuire wrote:...or just use Paul's formula with an if() for the special case...

With two variables you could save yourself a subtraction, viz:I suspect also that comparison with 0 is quicker, but it might all be offset by having an extra variable.

Ain't optimization fun?

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Consider Paul's rocket mass heater. |