Count All Distinct Pairs with Difference Equal to K in Java
In this tutorial, we are going to count all distinct pairs with difference equal to K in Java. Count every unique pair whose differences add up to k, given an integer array and a positive integer k.
Examples:
Example 1:
Input: array[ ] = {2, 4, 6, 8, 10}, k = 2
Output: 4
Explanation: There are four pairs {2, 4}, {4, 6}, {6, 8}, and {8, 10} that have a difference of 2.
Example 2:
Input: array[ ] = {1, 7, 5, 9, 2, 12, 3}, k = 2
Output: 4
Explanation: There are four pairs {1, 3}, {7, 9}, {5, 7}, and {3, 5} that have a difference of 2.
Example 3:
Input: array[ ] = {1, 11, 5, 3, 8}, k = 6
Output: 1
Explanation: There is one pair {5, 11} that have a difference of 6.
Approach 1: Using brute force
ALGORITHM:
Step 1: Initialize Counter
Step 2: Iterate through Elements of the array
Step 3: Check for Pairs
Step 4: Return Result
Filename: CountDistinctPairs.java
import java.util.*; import java.io.*; public class CountDistinctPairs { static int countPairsWithDiffK(int array[], int length, int diff) { int count = 0; // Select each component one at a time for (int x = 0; x < length; x++) { // Check to see if this selected element is present in pairs. for (int y = x + 1; y < length; y++) { if (array[x] - array[y] == diff || array[y] - array[x] == diff) { count++; } } } return count; } public static void main(String args[]) { int array[] = { 1, 7, 5, 9, 2, 12, 3}; int length = array.length; int diff = 2; System.out.println("Count of pairs with given diff is " + countPairsWithDiffK(array, length, diff)); } }
Output:
Count of pairs with given diff is 4.
Time complexity: The time complexity of the program is O(n2).
Space complexity: The program’s space complexity is O(1).
Approach 2: Using Sorting
ALGORITHM:
Step 1: Set the count to 0 upon startup.
Step 2: Arrange all of the numbers in ascending order.
Step 3: Take duplicates out of the array.
Step 4: Proceed as follows for every element arr[i].
Step 4.1: Search in binary from i+1 to n-1 for arr[i] + k in the subarray.
Step 4.2: If we find arr[i] + k, then count up.
Step 5: Return count.
Filename: CountDistinctPairs.java
import java.io.*; import java.util.*; public class CountDistinctPairs { // The typical binary search algorithm static int binarySearch(int array[], int low, int high, int target) { if (high >= low) { int mid = low + (high - low) / 2; if (target == array[mid]) return mid; if (target > array[mid]) return binarySearch(array, (mid + 1), high, target); else return binarySearch(array, low, (mid - 1), target); } return -1; } // Returns the number of pairs in array[] of size n that have a difference of k. static int countPairsWithDiffK(int array[], int length, int diff) { int count = 0, x; // Sort the elements in the array. Arrays.sort(array); // Select the first point in the element. for (x = 0; x < length; x++) { while (x - 1 >= 0 && array[x] == array[x - 1]) x++; if (binarySearch(array, x + 1, length - 1, array[x] + diff)!= -1) count++; } return count; } public static void main(String args[]) { int array[] = { 1, 7, 5, 9, 2, 12, 3}; int length = array.length; int diff = 2; System.out.println("Count of pairs with given diff is " + countPairsWithDiffK(array, length, diff)); } }
Output:
Count of pairs with given diff is 4.
Time complexity: The time complexity of the program is O(nlogn).
Space complexity: The program’s space complexity is O(logn).