1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 1/0.5=2 so 2 is not the lowest x or I missing something $\endgroup$ Nov 4, 2015 at 16:58
  • $\begingroup$ Assuming that the fractional part of $Y$ has at most $2$ decimal digits, calculate $d=\gcd(100Y,100)$ and the desired value of $X$ is $\frac{100}{d}$. $\endgroup$ Nov 4, 2015 at 17:04
  • $\begingroup$ Darn it. That means my examples might be flawed. The actual example should be 2 * .05 = A Whole Number. $\endgroup$ Nov 4, 2015 at 17:05
  • $\begingroup$ Your tags were way off. This has nothing whatsoever to do with either linear programming or divison algebras. The former is about optimization problems with linear constraints, the latter involves structures of abstract algebra (that many won't encounter until in grad school, but may meet examples in courses on abstract algebra). Did you read the tag wikis at all?? $\endgroup$ Nov 5, 2015 at 22:23

3 Answers 3

0
$\begingroup$

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)
$\endgroup$
2
  • $\begingroup$ I wouldn't prefer recursion on what he already have...even thought gcd answers the question. $\endgroup$ Nov 4, 2015 at 17:22
  • $\begingroup$ It looks like brute force is the simplest way to do it. $\endgroup$ Nov 5, 2015 at 10:28
0
$\begingroup$

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$

$\endgroup$
4
  • $\begingroup$ I think that OP will not understand the term "lowest terms" (I would use "simplest form" instead, but I think it would yield the same impact). So you might want to explain how to derive it from the original value (find the numerator and the denominator, and divide each one of them by their GCD, which I hope that OP might be able to understand). $\endgroup$ Nov 4, 2015 at 16:56
  • $\begingroup$ he is talking about prices in a shop, so it is kind of x.yz numbers $\endgroup$ Nov 4, 2015 at 16:57
  • $\begingroup$ It seems pretty silly to mention irrational numbers in the context of this question. $\endgroup$ Nov 4, 2015 at 16:57
  • $\begingroup$ @MichaelMedvinsky: The original post said $Y$ could be any real number. Otherwise, I would not have mentioned it. $\endgroup$ Nov 4, 2015 at 17:15
0
$\begingroup$

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}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .