Given an integer array arr[] and a positive integer K, the task is to count all distinct pairs with differences equal to K.
Examples:
Input: arr[ ] = {1, 5, 3, 4, 2}, K = 3
Output: 2
Explanation: There are 2 distinct pairs with difference 3, the pairs are {1, 4} and {5, 2}Input: arr[] = {8, 12, 16, 4, 0, 20}, K = 4
Output: 5
Explanation: There are 5 unique pairs with difference 4.
The pairs are {0, 4}, {4, 8}, {8, 12}, {12, 16} and {16, 20}
The naive approach and approach based on sorting and binary search are mentioned on the Set 1 of this article.
Approach: The time complexity for this problem can be reduced to have a linear complexity in average case by using hashing with the help of unordered maps as per the following idea:
For forming such unique pairs, if traversed from the smallest element, an element (say x) will form such a pair with another element having value (x+K).
When the difference K = 0 then the elements having frequency more than 1 will be able to form pairs with itself.
Follow the steps mentioned below to solve the problem:
- Initialize an unordered map and push all the array elements into the map.
- If the given value of K is 0:
- If the frequency of current element x is greater than 1, increment count by 1.
- Else try the same for the other elements.
- If the given value of K is not 0:
- Search x + K in the map and if it is found, increment the count by 1.
- Else try for the other elements.
- Return the count.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach.#include <bits/stdc++.h>using namespace std;// Function to find total pairsint TotalPairs(vector<int> nums, int K){ // Initializing a map unordered_map<int, int> mp; int cnt = 0; for (int i = 0; i < nums.size(); i++) { mp[nums[i]]++; } // Difference equal to zero if (K == 0) { for (auto i : mp) { // Frequency of element is // greater than one then // distinct pair is possible if (i.second > 1) cnt++; } } // Difference is not equal to zero else { for (auto i : mp) { // Frequency of element + k // is not zero then distinct // pair is possible if (mp.find(i.first + K) != mp.end()) { cnt++; } } } return cnt;}// Driver Codeint main(){ vector<int> arr = { 8, 12, 16, 4, 0, 20 }; int K = 4; // Function call int ans = TotalPairs(arr, K); cout << ans; return 0;} |
Java
// Java code to implement the above approach.import java.io.*;import java.util.*;class GFG { // Function to find total pairs public static int TotalPairs(int nums[], int K) { // Initializing a map Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); int cnt = 0; for (int i = 0; i < nums.length; i++) { if (mp.get(nums[i]) != null) mp.put(nums[i], mp.get(nums[i]) + 1); else mp.put(nums[i], 1); } // Difference equal to zero if (K == 0) { for (Map.Entry<Integer, Integer> it : mp.entrySet()) { // Frequency of element is // greater than one then // distinct pair is possible if (it.getValue() > 1) cnt++; } } // Difference is not equal to zero else { for (Map.Entry<Integer, Integer> it : mp.entrySet()) { // Frequency of element + k // is not zero then distinct // pair is possible if (mp.get(it.getKey() + K) != null) { cnt++; } } } return cnt; } public static void main(String[] args) { int arr[] = { 8, 12, 16, 4, 0, 20 }; int K = 4; // Function call int ans = TotalPairs(arr, K); System.out.print(ans); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 program for above approach# function to find total pairsdef TotalPairs(nums, K): # Initializing a map or dictionary mp = dict() cnt = 0 for i in range(len(nums)): if nums[i] in mp: mp[nums[i]] += 1 else: mp[nums[i]] = 1 # Difference equal to zero if K == 0: for i in mp: # Frequency of element is # greater than one then # distinct pair is possible if mp[i] > 1: cnt += 1 # Difference is not equal to zero else: for i in mp: # Frequency of element + k # is not zero then distinct #pair is possible if i + K in mp: cnt += 1 return cnt# Driver Codearr = [8, 12, 16, 4, 0, 20]K = 4# Function callans = TotalPairs(arr, K)print(ans)# This code is contributed by phasing17 |
C#
// C# code to implement the above approach.using System;using System.Collections.Generic;public class GFG { public static int TotalPairs(int[] nums, int K) { // Initializing a map Dictionary<int, int> mp = new Dictionary<int, int>(); int cnt = 0; for (int i = 0; i < nums.Length; i++) { if (mp.ContainsKey(nums[i])) mp[nums[i]] += 1; else mp[nums[i]] = 1; } // Difference equal to zero if (K == 0) { foreach(KeyValuePair<int, int> it in mp) { // Frequency of element is // greater than one then // distinct pair is possible if (it.Value > 1) cnt++; } } // Difference is not equal to zero else { foreach(KeyValuePair<int, int> it in mp) { // Frequency of element + k // is not zero then distinct // pair is possible if (mp.ContainsKey(it.Key + K)) { cnt++; } } } return cnt; } public static void Main(string[] args) { int[] arr = { 8, 12, 16, 4, 0, 20 }; int K = 4; // Function call int ans = TotalPairs(arr, K); Console.Write(ans); }}// This code is contributed by phasing17 |
Javascript
<script>// JavaScript program for the above approach// function to find total pairsfunction TotalPairs(nums, K){ // Initializing a map or dictionary var mp = {}; var cnt = 0; for (var i = 0; i < nums.length; i++) { if (mp.hasOwnProperty(nums[i])) mp[nums[i]] += 1; else mp[nums[i]] = 1; } // Difference equal to zero if (K == 0) { for (const i of Object.keys(mp)) { // Frequency of element is // greater than one then // distinct pair is possible console.log(i, mp[i], cnt); if (mp[i] > 1) cnt += 1; } } // Difference is not equal to zero else { for (const i of Object.keys(mp)) { // Frequency of element + k // is not zero then distinct // pair is possible\ if (mp.hasOwnProperty(parseInt(i) + K)) { cnt += 1; } } } return cnt;}// Driver Codevar arr = [ 8, 12, 16, 4, 0, 20 ];var K = 4;// Function call// var ans = TotalPairs(arr, K);document.write(TotalPairs(arr, K));// This code is contributed by phasing17</script> |
Output
5
Time Complexity: O(N) [In average case, because the average case time complexity of unordered map is O(1)]
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
