How to find the smallest integer X where the Remainder of X / Y = 0

Question

I am writing a grocery shopping program.

I want to calculate the smallest number of items I have to buy to reach the smallest whole dollar amount.

For example:

Candies cost 0.11. You need 100 candies to reach the nearest whole dollar amount 11

(100 * 0.11) = 11.0

Apples cost 0.5 each. you need 2 apples to reach the nearest dollar amount $1

(2 * 0.5) = 1.0

Ice Cream costs 4.82 You need 50 ice creams to reach the nearest whole dollar amount 241

(50 * 4.82) = 241.0

I THINK I am trying to solve the equation X % Y = 0 for X. X must be an integer. Y can be any positive rational number.

I can brute force the answer by running a simple loop:

var result : Number = ITEM_COST;

while(result % 1 != 0)
{
     result += ITEM_COST

}
return result / ITEM_COST;

However, I would like to have a more elegant calculation, if possible.

Answer 1

Assuming that the fractional part of $Y$ has at most $2$ decimal digits, the value of $X$ is $\frac{100}{\gcd(100Y,100)}$

Here is pseudo-code for calculating the GCD of two positive integers:

Function GCD(a,b):
    If a > b return gcd(a,b)
    Otherwise return gcd(b,a)

Function gcd(a,b):
    Set c = a mod b
    If c = 0 return b
    Otherwise return gcd(b,c)

Answer 2

If $Y$ is not rational, there is no number $X$ that will work. If $Y$ is rational, write it in lowest terms and $X$ is the denominator. So for your examples $0.11=\frac {11}{100}$ and $X=100$, $0.5=\frac 12$

Answer 3

You're looking for the smallest common multiple of $100$ and another number -- the price in cents. The number $100$ has no prime factors except $2$ and $5$: $$ 100 = 2\times2\times5\times5. $$

Say the price in cents is $3080$ (i.e., it's $\$30.80$). Look at how many $2$s and $5$s you can pull out of that. $$ 3080 = 2\times1540= 2\times2\times770 = 2\times2\times2\times385 = 2\times2\times2\times5\times77 $$ Three $2$s and one $5$. To get a multiple of $100$ you need at least two $2$s, and you've got those in this case, and at least two $5$s, and you have only one. So you need another $5$. So it takes five items to get an integer number of dollars: $$ 5\times \$30.80 = \$154.00 $$

Just multiply by as many $2$ and $5$s as are needed to get at least two $2$s and at least two $5$. If the price in cents is not divisible by $2$ or $5$, then you'll need two of each, so you'll multiply by $2\times2\times5\times5$, or $100$.

So in each case the number of items needed is: \begin{align} \text{either } & 1 & & = 1 \\ \text{or } & 2 & & =2 \\ \text{or } & 2\times 2 & & = 4 \\ \text{or } & 5 & & = 5 \\ \text{or } & 2\times 5 & & = 10 \\ \text{or } & 2\times2\times5 & & = 20 \\ \text{or } & 5\times5 & & =25 \\ \text{or } & 2\times5\times5 & & =50 \\ \text{or } & 2\times2\times5\times5 & & =100 \end{align}