Ch17 Greedy Algorithms and Invariants/Invariants boot camp

[BZAghalarov]

The Invariants boot camp section in EPI/Python given solution for two_sum problem(before 17.4 The3-sum problem). In a while loop condition given as "while i<=j" but I think it must be "while i<j". For the following entry it return true but it must return False. arr = [0,1,4,5,6], t = 8 Because 2th element 4 can't sum with itself.

[deveshks]

The question notes the following

For example, if the array is [11, 2, 5, 7, 3] then there are three entries in the array which add up to 21. (3, 7, 11 and 5,5, 11). (Note that we can use 5 twice, since the problem statement said we can use the same entry more than once.)

Hence the condition is while i<=j which will allow us to reuse a number twice

[tsunghsienlee]

@BZAghalarov , like what @deveshks said, this problem allows you to reuse the number, and the logic in the book is correct.

[BZAghalarov]

@deveshks your given example from "17.4 The 3-sum problem". But as I mentioned I write about previous(Invariants boot camp) section. And I must say that in your given problem hasn't any while loop part. For a clear understanding, I add text and code which part I have mentioned.

The most efficient approach uses invariants: maintain a subarray that is guaranteed to hold a solution, if it exists. This subarray is initialized to the entire array, and iteratively shrunk from one side or the other. The shrinking makes use of the sortedness of the array. Specifically, if the sum of the leftmost and the rightmost elements is less than the target, then the leftmost element can never be combined with some element to obtain the target. A similar observation holds for the rightmost element. def has-two-sum(A, t): i,j=0,len(A)-1 while i <= j: if A[i] + A[j] == t: return True elif A[i] + A[j] < t: i+=1 else: #Atil+A[j]>t j -= 1 return FaIse

P.S Problems sequence and numbering differs in books that are in different languages(for example Java <> Python)

[BZAghalarov]

@BZAghalarov , like what @deveshks said, this problem allows you to reuse the number, and the logic in the book is correct.

[deveshks]

I mentioned the 3 Sum problem since it uses the has_two_sum method which you have noted in your original question, and since the 3 sum problem mentions that we can use the same entry more than once.), I would assume that it holds true for has_two_sum as well.

But yes, I do agree that it should be explicitly mentioned in the boot camp section to avoid any ambiguity

[BZAghalarov]

Yes, I incorrectly think it separately written for two sum problem which does not include the same element twice. @deveshks thank you for an explanation.