0

The problem is:

Given an array of floating pointer numbers, find 3 numbers (not necessarily contiguous) that sum to a value bounded by the interval [1.0, 2.0]

This problem was posted here Triplet whose sum in range (1,2) and also https://www.thetopsites.net/article/50729117.shtml.

The algorithm in the latter link appears to be identical to the algorithm posted by @Amitrajit Bose in the stackoverflow question. This algorithm essentially uses a greedy approach that discards the largest of the current set of 3 numbers you're considering if the sum is > 2.0 and replaces it with the current number in the array, and if the sum is < 1.0, it replaces the smallest number in the current set of 3 numbers.

This algorithm seems wrong? Consider [0.2 0.2 1.7 0.5 0.05 0.05]. There are several solutions in this case and they must each use 1.7, but this algorithm would the number 1.7 and conclude that it is not possible to find a triplet under the given constraints.

Am I misunderstanding something?

roulette01
  • 1,984
  • 2
  • 13
  • 26

1 Answers1

0

Yes, you are right. Such algorithm is wrong, you just provided a test case where it fails.

Mentioned algorithm:

1> Prepare the window of size 3 with the first 3 elements
2> IF (array.len <= 3): CHECK IF window-sum is in the range (1,2), then RETURN accordingly
3> FOR i = 3 UPTO (array.len-1)
3.1> SORT the window (3log3 = constant time operation)
3.2> IF window-sum is in the range (1,2): RETURN 1 or TRUE
3.3> ELSE IF window-sum < 1: Replace the smallest element in the window (window[0]) with array[i]
3.4> ELSE IF window-sum > 2: Replace the largest element in the window (window[2]) with array[i]
4> Outside the loop, check the FINAL window sum and RETURN accordingly.

Another counterexample: [0.2, 0.3, 0.4, 1.5]
First window is [0.2, 0.3, 0.4]. The for loop starts and ends at index 3 where window_sum = 0.9 < 1. Step 3.3 is taken so next window is [0.3, 0.4, 1.5] where window_sum = 2.2 > 2. The algorithm ends claiming that there is no such triplet whose sum is in [1.0, 2.0]. Such claim is false as (0.2, 0.3, 1.5) sums 2.0.

Side note: There are a few more incorrect answers in that stackoverflow question.

Eloy Pérez Torres
  • 1,050
  • 4
  • 14