programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Devaka Cooray
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Jeanne Boyarsky
• Tim Cooke
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Tim Moores
• Mikalai Zaikin
• Carey Brown
Bartenders:

# Algorithm help: minimum distance to multiple

Ranch Hand
Posts: 1296
• Number of slices to send:
Optional 'thank-you' note:
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?

Marshal
Posts: 28000
94
• Number of slices to send:
Optional 'thank-you' note:
Some quick scribbling suggests to me that

b - (a % b)

works just as well. Am I right?

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.

Bartender
Posts: 1205
22
• Number of slices to send:
Optional 'thank-you' note:

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.

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
Bartender
Posts: 1205
22
• Number of slices to send:
Optional 'thank-you' note:
...or just use Paul's formula with an if() for the special case:

One MOD, one subtraction, one comparison and one extra assignment one time out of b on average. The comparison and possibly extra assignment are probably cheaper computationally than a second MOD.

Ranch Hand
Posts: 30
• Number of slices to send:
Optional 'thank-you' note:
result = (b^2 - a)

result = result % b

clean ? :-)

Ryan McGuire
Bartender
Posts: 1205
22
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:

Ryan McGuire wrote:
This assumes that b^2 > a.

great catch .

if a >= b ^2 then a = a % b then do rest .. . please post further if you find any other hole ....

edit:

i.e, pre condition -> if a = 0 then result = b

f(a, b) then convert f(a % b , b) first .

Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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

 Now I am super curious what sports would be like if we allowed drugs and tiny ads. a bit of art, as a gift, that will fit in a stocking https://gardener-gift.com