-1

So I've been attempting to solve the 3SUM problem and the following is my algorithm

def findThree(seq, goal):
    for x in range(len(seq)-1):

        left = x+1
        right = len(seq)-1

        while (left < right):
            tmp = seq[left] + seq[right] + seq[x]
            if tmp > goal:
                right -= 1
            elif tmp < goal:
                left += 1
            else:
                return [seq[left],seq[right],seq[x]]

As you can see it's a really generic algorithm that solves it in O(n2).

The problem I've been experiencing is that this algorithm doesn't seem to like working with floating point numbers.

To test that my theory is right, I gave it the following two array

FloatingArr = [89.95, 120.0, 140.0, 179.95, 199.95, 259.95, 259.95, 259.95, 320.0, 320.0]
IntArr = [89, 120, 140, 179, 199, 259, 259, 259, 320, 320]


findThree(FloatingArr, 779.85) // I want it to return [259.95, 259.95, 259,95]
>> None // Fail
findThree(FloatingArr, 777) // I want it to return [259,259,259]
>> [259, 259, 259] // Success

The algorithm does work, but it doesn't seem to work well with floating point numbers. What can I do to fix this?

For additional information, my first array is originally a list of string of prices, but in order to do math with them, I had to strip the "$" sign off. My approach in doing so is this

for x in range(len(prices)):
    prices[x] = float(prices[x][1:]) // return all the prices without the "$" sign. Casting them to float.

If there is a much better way, please let me know. I feel as if this problem is not really about findThree() but rather how I modified the original prices array.

Edit: Seeing that it is indeed a floating point problem, I guess my next question would be what is the best way to convert a string to int after I strip off the "$" ?

user3277633
  • 1,891
  • 6
  • 28
  • 48

2 Answers2

0

It doesn't work because numbers like 89.95 typically cannot be stored exactly (because the base-two representation of 0.95 is a repeating decimal).

In general, with dealing with floating-point numbers, instead of comparing for exact equality via ==, you want to check if the numbers are "close enough" to be considered equal; typically done with abs(a - b) < SOME_THRESHOLD. The exact value of SOME_THRESHOLD depends on how accurate you want to be, and typically requires trial and error to get a good value.

In your specific case, because you're working with dollars and cents, you can simply convert to cents by multiplying by 100 and rounding to an integer (via round, because int will round ie 7.999999 to 7). Then, your set of numbers will just be integers, solving the rounding problem.

Drew McGowen
  • 11,471
  • 1
  • 31
  • 57
0

You can convert your prices from string to integers instead of converting them to floats. Let's assume that all prices have at most k digits after the decimal point(in initial string representation). Then 10^k * price is always a whole number. So you completely can get rid of floating-point computations.

Example: if there are at most two digits after the decimal point, $2.10 becomes 210 and $2.2 becomes 220. There is no need to use float even in intermediate computations because you can shift decimal point by two positions to the right(appending zeros if necessary) and then convert a string directly to an integer.

Here is an example of convert function:

def convert(price, max_digits):
    """ price - a string representation of the price
        max_digits - maximum number of digits after a decimal point
                     among all prices
    """
    parts = price[1:].split('.')
    if len(parts) == 2 and len(parts[1]) > 0:
        return int(parts[0]) * 10 ** max_digits + \
               int(parts[1]) * 10 ** (max_digits - len(parts[1]))
    else:
        return int(parts[0]) * 10 ** max_digits
kraskevich
  • 18,368
  • 4
  • 33
  • 45