<jupyter_start><jupyter_text>2-SUM AlgorithmThe goal of this problem is to implement a variant of the 2-SUM algorithm covered in this week's lectures.The file algo1-programming_prob-2sum.txt contains 1 million integers, both positive and negative (there might be some repetitions!).This is your array of integers, with the ith row of the file specifying the ith entry of the array.Your task is to compute the number of target values t in the interval [-10000,10000] (inclusive) such that there are distinct numbers x,y in the input file that satisfy x+y=t. (NOTE: ensuring distinctness requires a one-line addition to the algorithm from lecture.)Write your numeric answer (an integer between 0 and 20001) in the space provided.OPTIONAL CHALLENGE: If this problem is too easy for you, try implementing your own hash table for it. For example, you could compare performance under the chaining and open addressing approaches to resolving collisions.<jupyter_code># Binary search function for finding the index at which a value should be at.
# return the index above if the value is found
# If the value is not found, return the index of the next higher value
def find_index_low(arr, start, end, t):
    # Where to insert a value
    if end == start:
        if arr[start] > t:
            return start
        else:
            return start+1
        
    mid = int((end+start)/2)
    center = arr[mid]
    
    if t > center:
        return find_index_low(arr, mid+1, end, t)
    else:
        return find_index_low(arr, start, mid, t)

# Test
arr = [-10, 1 ,3, 4, 6, 9, 11, 14]
print (find_index_low(arr, 0, len(arr)-1, 5))
file = "algo1-programming_prob-2sum.txt"

_arr = [int(i) for i in open(file, "r").readlines()]
arr = sorted(_arr)

c = 10000
n=len(arr)-1
mySum = {}
count = 0
for x in arr:
    mySet = set()
    
    #print ("for",x, "find a num between",-c-x, c-x)
    i_low = find_index_low(arr, 0, n, -c - x)    
    i_up = find_index_low(arr, 0, n, c - x)
    
    mylist = arr[i_low:i_up]
        
    if x in mylist:
        mylist.remove(x)
    
    for m in mylist:
        mySum[x+m] = True
        
print (len(mySum.items()))<jupyter_output>427
{'fraction_non_alphanumeric': 0.09074074074074075, 'fraction_numerical': 0.024074074074074074, 'mean_word_length': 3.1319311663479925, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '583011', 'license': 'MIT', 'n_tokens_mistral': 727, 'n_tokens_neox': 677, 'n_words': 289, 'path': '2-sum/2-sum.ipynb', 'repo_name': 'jazracherif/algorithms', 'size': '2160'}