Pairs Hackerrank problem solution

Given N integers, count the number of pairs of integers whose difference is K.

Input Format

The first line contains N and K.
The second line contains N numbers of the set. All the N numbers are unique.

Constraints

2<=N<=105
0<=K<=109
Each integer will be greater than 0 and at least K smaller than 231-1.
Output Format

An integer that tells the number of pairs of integers whose difference is K.

<strong>Sample Input</strong>
5 2
1 5 3 4 2
<strong>Sample Output</strong>
3

Explanation

There are 3 pairs of integers in the set with a difference of 2.

Solution

The first observation we can make is that we don’t need to enumerate all N^2 pairs and then check whether the pairs of integers have a difference of K.

What we simply need to do is – for each integer N, check whether the original array contains N-K and N+K. In fact, we can iterate over each number N in the original array and check whether N+K exists in the same array. So basically we need a data structure supporting fast membership inquiry.

Two of the most popular data structures supporting this operation are binary search tree and hash table. The former supports O(logN) time complexity, while the latter supports O(1) time complexity.

Most programming languages already support these data structures in their library functions. For example, if you want to use a binary search tree in C++, you can use STL set; if you want to use a hash table in C++, you can use unordered_set.

It is easy to test the performance of both set and unordered_set. And you can see that unordered_set does run faster than set, which in turn validates the advantage over time complexity.

#include <iostream>
#include <algorithm>
using namespace std;
/* Head ends here */


/* Tail starts here */
int main() {
  long long n,d;
    cin>>n>>d;
long long a[n];
for(int i=0;i<n;i++)
cin>>a[i];

sort(a,a+n);

long long j=0,k=n-1,count=0,yes=0; 
while(j<n)
{
    while(abs(a[j]-a[k])>d &&k>0&& yes==0)
        --k;
    while(abs(a[j]-a[k])<d &&k<n-1&& yes==1)
        ++k;
    if(abs(a[j]-a[k])==d){
        ++count;
        yes=1;
    }
    if(yes==0)
        k=n-1;
    ++j;

    }
cout<<count;    
    return 0;
}
#include<iostream>
#include<unordered_set>
using namespace std;

unordered_set<int> s;

int main()
{
    int n, k, val;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> val;
        s.insert(val);
    }
    int ans = 0;
    for (unordered_set<int>::iterator it = s.begin(); it != s.end(); ++it)
        if (s.find(*it + k) != s.end()) ans++;
    cout << ans << endl;
    return 0;
}
dic={}
n,k=map(int,raw_input().split())
l=map(int,raw_input().split())
for i in l:
	dic[i]=True
ans=0
for i in dic:
	if i+k in dic:
		ans+=1
print ans
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    static int pairs(int[] a,int k) {
        Arrays.sort(a);
        int N = a.length;
		int count = 0;
		for (int i = 0; i < N - 1; i++)
		{
			int j = i + 1;
			while((j < N) && (a[j++] - a[i]) < k);
			j--;
			while((j < N) && (a[j++] - a[i]) == k)
				count++;			
		}

        return count;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int res;
        
        String n = in.nextLine();
        String[] n_split = n.split(" ");
        
        int _a_size = Integer.parseInt(n_split[0]);
        int _k = Integer.parseInt(n_split[1]);
        
        int[] _a = new int[_a_size];
        int _a_item;
        String next = in.nextLine();
        String[] next_split = next.split(" ");
        
        for(int _a_i = 0; _a_i < _a_size; _a_i++) {
            _a_item = Integer.parseInt(next_split[_a_i]);
            _a[_a_i] = _a_item;
        }
        
        res = pairs(_a,_k);
        System.out.println(res);
    }
}

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin @coderinme

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.