Find all pairs of elements within an array that sum up to a given value

user_2581360 0
Viewed 3056

I am stuck in one of Hackerrank problems with following problem description :-

You will be given an array of integers and a target value. Determine the number of pairs of array elements that have a difference equal to a target value.

For example, given an array of [1, 2, 3, 4] and a target value of 1, we have three values meeting the condition: (2,1), (3,2), (4,3). So function pairs should return value 3.

We have to implement pairs function with following parameters :-

k: an integer, the target difference
arr: an array of integers

Constraints :-

1> Each Integer in arr[i] will be unique and positive.
2> target k will also be positive.

My below function implementation is failing one of 18 test cases because of the wrong result. Can anyone please help me debug the issue :-

def binSearch(target,arr):
    lower = 0
    upper = len(arr)-1
    while lower <= upper:
        mid = int((lower + upper)/2)
        if(arr[mid] == target):
            return 1
        elif(arr[mid] > target):
            upper = mid - 1
        elif(arr[mid] < target):
            lower = mid + 1
    return -1

def pairs(k, arr):
    arr.sort()
    count = 0
    for i in range(len(arr)):
        target = abs(arr[i] - k)
        if(arr[i] == target):
            pass
        elif(binSearch(target,arr) == 1):
            count += 1
    return count
algorithm python debugging
2 Answers

This should be an O(n) solution (where n is the size of arr). First, convert the array to a set. Then iterate through each value in arr and check if arr + k is in the set, i.e. the difference between the other value and the current value val is equal to k. If so, increment counter by one.

def pairs(k, arr):
    counter = 0
    set_arr = set(arr)
    for val in arr:
        if val + k in set_arr:
            counter += 1
    return counter
user_24118020

By java, for rum time it will take O(n log n) to sort the array, and for binary search it takes O(log m) so O(n log n + log m) == > O(n log n) space it will take O(n)

public static ArrayList<Pair<Integer, Integer>> pairThatHaveDiffrenceK(int[] arr , int arrLength , int k ){



        ArrayList<Pair<Integer, Integer>> arrayList = new ArrayList<>();
        Arrays.sort(arr);

        for (int i = 0; i < arrLength ; i++) {
            temp = arr[i] + k;
            int testIfFound = indexFromBinarySearch(arr, temp);
            if (testIfFound != -1){
                arrayList.add(new Pair<>(arr[i],arr[testIfFound] ));
           }
        }

        return arrayList ;
    }


    public static int indexFromBinarySearch(int[] arr, int valueForTarget){
        int start =0 ;
        int end = arr.length-1;
        while (start <= end){
            int mid = (start+end)/2 ;
            if(arr[mid] == valueForTarget){
                return mid;
            }
            else if(valueForTarget > arr[mid])
                start =mid+1;
            else
                end = mid-1;

        }
        return -1 ;
    }
user_79003510
Related