Win a copy of Beginning Java 17 Fundamentals: Object-Oriented Programming in Java 17 this week in the Java in General forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
...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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
result = (b^2 - a)

result = result % b

clean ? :-)
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
reply
    Bookmark Topic Watch Topic
  • New Topic