dimanche 14 mai 2017

Code complexity analysis for find out the number of pairs in the array that add to produce the given number. [on hold]

Given an array and a number I would like to find out the number of pairs in the array that add to produce the given number.

There are four approaches and would like the get you opinion on the different approach for solving the problem also if you think there is a better way to do it please share an example for the same.

public class ArrayQuestions {

public int findNumberOfPairs(int[] arr, int number) {
    int count = 0;
    if (arr != null) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length && arr[i] < 7; j++) {
                if (arr[i] + arr[j] == number) {
                    System.out.println("{" + arr[i] + "," + arr[j] + "}");
                    count++;
                }
            }
        }
    }
    return count;
}

public int numberOfPairsAfterSorting(int[] arr, int number) {
    Objects.requireNonNull(arr);
    Arrays.sort(arr);
    int count = 0;
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == number) {
            count++;
            left++;
        } else if (sum < number) {

            left++;
        } else {
            right--;
        }
    }
    return count;
}

public int findPairsUsingBooleanArray(int[] arr, int number) {
    boolean[] visited = new boolean[100];
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        int difference = number - arr[i];
        if (difference > -1 && visited[difference]) {
            count++;
        }
        visited[arr[i]] = Boolean.TRUE;
    }
    return count;
}

public int findPairsUsingSet(int[] arr, int number) {
    Set<Integer> visited = new HashSet<>();
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        int difference = number - arr[i];
        if (visited.contains(difference)) {
            count++;
        }
        visited.add(arr[i]);
    }
    return count;
}

}

Aucun commentaire:

Enregistrer un commentaire