Search code examples
algorithmmathpseudocode

Algorithm to find next multiple

Given two positive integers x and y, I need to find the next number greater than or equal to x that is a multiple of y.

For example:

x=18, y=3 => 18

or

x=18, y=5 => 20

or

x=121, y=25 => 125

My first thought was to keep incrementing x until I find a match but that can get fairly inefficient for high y values.

Then I thought about x - (x % y) + y but that wont work if x is a multiple of y. Of course, I can always adjust for that using a ternary operator in the formula x - ((x % y)==0?y:x % y) + y.

Does anyone have any good, clever, simple suggestions or a complete solution that is better than what I have touched on? Am I missing something obvious in my logic?

I'll be using Java (this is a small piece of a greater algorithm), but pseudocode would be just as helpful if it is all straight math.

Solution

  • If x and y are positive ints then this will work:

    y * ((x-1)/y + 1);

    Using the x-1 allows you to not have to worry about the special case when x is a multiple of y. For example, if y = 5, then for 16 <= x <= 20,

    15 <= x-1 <= 19
(x-1)/y == 3
(x-1)/y+1 == 4
y*((x-1)/y+1) == 20