GitHub / shivangi-975 / Dynamic-2-SUM

Consider the 2-SUM problem: given an array of n integers (possibly with repetitions), and a target integer t find if there exist two distinct elements x, y in the array such that x + y = t. There are multiple approaches to find a O(n log n) solution to this problem. We would like to implement a dynamic version of this problem. In this version, you do not know the number of elements in advance. The input arrives as a sequence of operations. We start with the empty multiset S. Operations are of three types: 1. Insert(k) : Inserts a number k into S. 2. Delete(k): Deletes an instance of the key k from S. If k is not present, no change is made to the data structure. If k is present multiple times, any one instance is deleted. 3. Query (a, b): Prints the number of target values in the closed interval [a, b] such that there are distinct elements x, y in the multiset with x + y = t. Note that by “distinct” above, we mean two distinct elements of the multiset, which could have the same integer value. E.g. if S = {5, 5, 5}, then then Query (10,15) returns the answer 1, whereas Query(17,20) returns the answer 0.

JSON API: http://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/shivangi-975%2FDynamic-2-SUM
PURL: pkg:github/shivangi-975/Dynamic-2-SUM

Topics: arraylist, search-algorithm, sorting-algorithms, stringbuilder-class-java

• Files
• Readme
• Dependencies
• Releases