Greedy Algorithms — Avoid division comparisons in comparators

Soution to avoiding division comparisons

Photo by Jesper Aggergaard on Unsplash

This is to keep track and document concept I lerned for future revision. While solving greedy algorithm problems, fractions may encounter

def comparator(a: int, b: int):
  # a should come before b when (a.price/a.weight) > (b.price/b.weight)
  return (a.price/a.weight) > (b.price/b.weight)

# a.price/a.weight generates fraction
# b.price/b.weight generates fraction

As a and b are integers. 7/2=3 and 6/2=3 will the below contition be true? NO Condition: (a.price/a.weight) > (b.price/b.weight)

Ideal works when we make it float division, by multiplying 1.0 (7/2)1.0 and (6/2)1.0

This can work but it still may suffer from precision related issues. Every decimal or float or double datatype has some level of precisions, or number of places after decila point.

There must be a problem while comparing fractions. There can have limited number of decimals, say only 4 places after decimal point. is there ant solution where this kind of divirion can be avoided?

Solution is that do cross multiplication. a/b > c/d implies that ad > bc

This is the standard technique to avoid the divisions and decimal places related problems.

Greedy algorithms, where there are going to be lot of custom greeds, where such comparators to be written. Avoid the divisions as much as possible.

Feel free to reach out on LinkedIn for networking.