Get the GitHub solution and source code github.com/KodeLoad/DailyKodePractice/tree/mainline/GeeksForGeeks/TwoSum%E2%80%93PairWithGivenSum Also contribute within the repo, with your favorite language like C++, Rust, Go, JavaScript, Java, Typescript, and much more but most important, keep koding.
But there will be the problem of self pairing in the solution of binary search, like to avoid the self pairing we are not using the pre-filled set right? then how will we avoid the self pairing in the solution while using for loop and binary search
Well within the solution of binary search, the question no where says that we cannot use duplicate number's as long as duplicate number's exists within an array. So for target_sum = 4 in array of [1, 2, 2, 4, 9] the answer is true as we have [2, 2] (ie, index 1 and index 2). But, having said that, if the array was [1, 2, 4] then it would be false, due to the self pairing as you mentioned. Self pairing is avoided in our code. But how? You see if we look upon the code, we consider an index let say i, now we don't want this i index to occur again, so we search from [i + 1 to end of array] you can reffer to this line : github.com/KodeLoad/DailyKodePractice/blob/14b0d8d55f357e936c540e58dc0354f33c37d265/GeeksForGeeks/TwoSum%E2%80%93PairWithGivenSum/BinarySearchSolution.java#L18 Likewise we are not missing upon the element's as well nor repeating any index. Hope this satisfies the question, and glad to see that you guys are keen upon details🧡.
Hmmm, Not actually, Let's say for an array a simple searching, we have complexity : log n we need to search for : (n-1) item's lets say n items so, overall search = n * log n that means for each item within the array, search for the counterpart, here's a source-code if you wanted to refer to github.com/KodeLoad/DailyKodePractice/blob/mainline/GeeksForGeeks/TwoSum%E2%80%93PairWithGivenSum/BinarySearchSolution.java
@@obrutus okay i get it, i was thinking time complexity of binary search as O(n logn) and then a loop over it, so i said O(n*n(logn)) , my mistake....and thanks for explaining. 💟
![I.N "HALLUCINATION" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/n5B5q1Hwt_U/mqdefault.jpg)
Get the GitHub solution and source code
github.com/KodeLoad/DailyKodePractice/tree/mainline/GeeksForGeeks/TwoSum%E2%80%93PairWithGivenSum
Also contribute within the repo, with your favorite language like C++, Rust, Go, JavaScript, Java, Typescript, and much more
but most important, keep koding.
But there will be the problem of self pairing in the solution of binary search, like to avoid the self pairing we are not using the pre-filled set right? then how will we avoid the self pairing in the solution while using for loop and binary search
Well within the solution of binary search, the question no where says that we cannot use duplicate number's as long as duplicate number's exists within an array. So for target_sum = 4 in array of [1, 2, 2, 4, 9] the answer is true as we have [2, 2] (ie, index 1 and index 2).
But, having said that, if the array was [1, 2, 4] then it would be false, due to the self pairing as you mentioned. Self pairing is avoided in our code.
But how?
You see if we look upon the code, we consider an index let say i, now we don't want this i index to occur again, so we search from
[i + 1 to end of array]
you can reffer to this line : github.com/KodeLoad/DailyKodePractice/blob/14b0d8d55f357e936c540e58dc0354f33c37d265/GeeksForGeeks/TwoSum%E2%80%93PairWithGivenSum/BinarySearchSolution.java#L18
Likewise we are not missing upon the element's as well nor repeating any index.
Hope this satisfies the question, and glad to see that you guys are keen upon details🧡.
binary search logic should be of time complexity O(n*n log n)??
Hmmm, Not actually,
Let's say for an array
a simple searching, we have complexity : log n
we need to search for : (n-1) item's lets say n items
so,
overall search = n * log n
that means for each item within the array, search for the counterpart,
here's a source-code if you wanted to refer to
github.com/KodeLoad/DailyKodePractice/blob/mainline/GeeksForGeeks/TwoSum%E2%80%93PairWithGivenSum/BinarySearchSolution.java
@@obrutus okay i get it, i was thinking time complexity of binary search as O(n logn) and then a loop over it, so i said O(n*n(logn)) , my mistake....and thanks for explaining. 💟