HackerRank Pairs Problem Solution

In this post, we will solve HackerRank Pairs Problem Solution.

Given an array of integers and a target value, determine the number of pairs of array elements that have a difference equal to the target value.
Example
k = 1
arr = [1, 2, 3, 4]
There are three values that differ by k = 1:2-1=1,321, and 4-3 = 1. Return
3.

Function Description

Complete the pairs function below.

pairs has the following parameter(s):

int k: an integer, the target difference
int arr[n]: an array of integers

Returns

int: the number of pairs that satisfy the criterion

Input Format
The first line contains two space-separated integers n and k, the size of arr and the target
value.
The second line contains n space-separated integers of the array arr.

Sample Input

STDIN       Function
-----       --------
5 2         arr[] size n = 5, k =2
1 5 3 4 2   arr = [1, 5, 3, 4, 2]

Sample Output

Explanation

There are 3 pairs of integers in the set with a difference of 2: [5,3], [4,2] and [3,1]. .

Table of Contents

Pairs C Solution

#include <stdio.h>
#include <stdlib.h>

#define PARENT(i) ((i+1)/2 - 1)
#define LEFT(i) (2*i+1)
#define RIGHT(i) (2*i+2)

void swap(int *arr, int i, int j){
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

void max_heapify(int *in, int i, int heap_size){
  int l = LEFT(i);
  int r = RIGHT(i);
  int largest = i;

  if(l<heap_size && in[l]>in[i])
    largest = l;
  if(r<heap_size && in[r]>in[largest])
    largest = r;

  if(largest != i){
    swap(in, i, largest);
    max_heapify(in, largest, heap_size);
  }
}

void build_heap(int *in, int heap_size){
  int i;
  for(i = PARENT(heap_size-1); i>=0; i--){
    max_heapify(in, i, heap_size);
  }
}

void heap_sort(int *in, int n){
  int i;
  for(i=0; i<n; i++){
    swap(in, 0, n-i-1);
    max_heapify(in, 0, n-i-1);
  }
}

int npairs(int *arr, int n, int k){
  int i=0, j=0, count=0;
  for(; i<n; i++){
    for(; j<n; j++){
      if(arr[j] > arr[i]+k)
        break;
      else if(arr[j] == arr[i]+k){
        count++;
        break;
      }
    }
    if(j>=n)
      break;
  }
  return count;
}

int main(){
  int n, k, i;
  scanf("%d %d", &n, &k);

  int *arr = (int *)malloc(n*sizeof(int));
  for(i=0; i<n; i++)
    scanf("%d", arr+i);

  build_heap(arr, n);

  heap_sort(arr, n);

  printf("%d", npairs(arr, n, k));
  free(arr);

  return 0;
}

Pairs C++ Solution

/****************	https://www.hackerrank.com/challenges/pairs	*****************/

#include<iostream>
#include<cstring>
#include<cmath>
#include<bits/stdc++.h>
#include<vector>
#include<bitset>
#include<map>
#include<unordered_map>
#include<iterator>
#include<iostream>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdlib>
#include<limits.h>
#define MOD 1000000007
using namespace std;


int binary_search(int a[], int n, int low,int key)
{
	int high=n-1;
	int mid= (high+low)/2;
	while(1)
	{
		if(low > high)
			return -1;
		if(key > a[mid])
			low=mid+1;
		else if(key < a[mid])
			high=mid-1;
		else
			return mid;
		mid= (low+high)/2;
	}
}
int main()
{
	std::ios_base::sync_with_stdio(false);
	int n,k,ans;
	cin>>n>>k;
	int a[n];
	ans=0;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	for(int i=0;i<n;i++)
	{
		int index= binary_search(a,n,i+1,a[i]+k);
		if(index!= -1)
			ans++;
	}
	cout<<ans<<endl;
}

Pairs C Sharp Solution

using System;
using System.Collections.Generic;

namespace Balmatlab
{
    class Solution
    {
        static void Main(string[] args)
        {
            
            string firstLine = Console.ReadLine();
            string[] splitFirstLine = firstLine.Split(' ');
            int length = int.Parse(splitFirstLine[0]);
            int diff = int.Parse(splitFirstLine[1]);

            string str = Console.ReadLine();
            int count = 0;

            string[] arr = str.Split(' ');

            Dictionary<string, string> arrList = new Dictionary<string, string>();
            if (arr.Length > 0)
            {
                for (int i = 0; i < arr.Length; i++)
                {
                    arrList.Add(arr[i], string.Empty);
                }
            }

            for (int i = 0; i < arr.Length; i++)
            {
                int result = 0;
                int numberToCompare = int.Parse(arr[i]);
                if ((result = numberToCompare - diff) > 0)
                {
                    if (arrList.ContainsKey(result.ToString()))
                    {
                        count++;
                    }
                }
            }
            Console.WriteLine(count);
        }

    }
}

Pairs Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'pairs' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER k
     *  2. INTEGER_ARRAY arr
     */

    public static int pairs(int k, List<Integer> arr) {
        Collections.sort(arr);
        int count = 0;
        int i = arr.size() - 1;
        int j = arr.size() - 1;
        while(i >= 0) {
            if(arr.get(j) - arr.get(i) == k) {
                i--;
                count++;
            }else if(arr.get(j) - arr.get(i) > k) {
                j--;
            }else {
                i--;
            }
        }
        return count;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int k = Integer.parseInt(firstMultipleInput[1]);

        List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        int result = Result.pairs(k, arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Pairs JavaScript Solution

function trim(s) {
    return s.replace(/^\s+|\s+$/g, '');
}
function tokenize(s) {
    return trim(s).split(/\s+/);
}
function tokenizeIntegers(s) {
    var tokens = tokenize(s);
    for (var i = 0; i < s.length; ++i) {
        tokens[i] = parseInt(tokens[i]);
    }
    return tokens;
}

function processData(input) {
    var lines = input.split('\n');
    var integers = tokenizeIntegers(lines[0]);
    var n = integers[0], delta = integers[1];
    var nums = tokenizeIntegers(lines[1]);
    var hash = {};
    for (var i = 0; i < n; ++i) {
        hash[nums[i]] = true;
    }
    var count = 0;
    for (var i = 0; i < n; ++i) {
        if(hash[nums[i]+delta]) {
            ++count;
        }
    }
    process.stdout.write(count+"\n");
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Pairs Python Solution

N, K = [int(x) for x in input().split()]

A = [int(x) for x in input().split()]

A.sort()

j = 0
answer = 0
for i in range(len(A)):
    while j < len(A) and A[j] < A[i] + K:
        j += 1
    if j < len(A) and A[j] == A[i] + K:
        answer += 1
print(answer)