Win a copy of Beginning Java 17 Fundamentals: Object-Oriented Programming in Java 17 this week in the Java in General forum!
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:
• Tim Cooke
• Campbell Ritchie
• Ron McLeod
• Liutauras Vilda
• Jeanne Boyarsky
Sheriffs:
• Junilu Lacar
• Rob Spoor
• Paul Clapham
Saloon Keepers:
• Tim Holloway
• Tim Moores
• Jesse Silverman
• Stephan van Hulst
• Carey Brown
Bartenders:
• Al Hobbs
• Piet Souris
• Frits Walraven

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?

Sheriff Posts: 26966
84   • • 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 With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.