Hackerrank Pairs Solution
.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
You will be given an array of integers and a target value. Determine the number of pairs of array elements that have a difference equal to a target value.
For example, given an array of [1, 2, 3, 4] and a target value of 1, we have three values meeting the condition: , , and .
Function Description
Complete the pairs function below. It must return an integer representing the number of element pairs having the required difference.
pairs has the following parameter(s):
- k: an integer, the target difference
- arr: an array of integers
Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
The first line contains two space-separated integers and , the size of and the target value.
The second line contains space-separated integers of the array .
Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
- each integer will be unique
Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
An integer representing the number of pairs of integers whose difference is .
Sample Input.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}
5 2
1 5 3 4 2
Sample Output.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}
3
Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
There are 3 pairs of integers in the set with a difference of 2: [5,3], [4,2] and [3,1] .
Solution in java8
Approach 1.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[] c = new int[n];
for (int i = 0; i < n; i++) {
c[i] = in.nextInt();
}
Arrays.sort(c);
int i = c.length - 1;
int j = c.length - 1;
int count = 0;
while (i > 0) {
while(c[i] - c[j] < k && j > 0) j--;
if (c[i] - c[j] == k) count++;
i--;
}
System.out.println(count);
in.close();
}
}
Approach 2.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int pairCount = 0;
Set<Integer> seen = new HashSet<>();
for (int i = 0; i < n; i++) {
int x = in.nextInt();
if (Integer.MAX_VALUE - k >= x && seen.contains(x + k)) {
pairCount++;
}
if (Integer.MIN_VALUE + k <= x && seen.contains(x - k)) {
pairCount++;
}
seen.add(x);
}
System.out.println(pairCount);
}
}
Approach 3.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[] numbers = new int[n];
for(int i=0; i<n; i++) {
numbers[i] = in.nextInt();
}
Arrays.sort(numbers);
int count = 0;
for(int i=0; i<n; i++) {
for(int j=i; j<n; j++) {
if(numbers[j] - numbers[i] > k) {
break;
}
if(Math.abs(numbers[i] - numbers[j]) == k) {
count++;
}
}
}
System.out.println(count);
}
}
Solution in python3
Approach 1.
#!/usr/bin/py
# Head ends here
def pairs(a,k):
# a is the list of numbers and k is the difference value
return len(set(a) & set(x + k for x in a))
# Tail starts here
if __name__ == '__main__':
a = input().strip()
a = list(map(int, a.split(' ')))
_a_size=a[0]
_k=a[1]
b = input().strip()
b = list(map(int, b.split(' ')))
print(pairs(b,_k))
Approach 2.
#!/usr/bin/py
# Head ends here
def pairs(a,k):
# a is the list of numbers and k is the difference value
answer = len(set(a) & set(x+k for x in a))
return answer
# Tail starts here
if __name__ == '__main__':
a = input().strip()
a = list(map(int, a.split(' ')))
_a_size=a[0]
_k=a[1]
b = input().strip()
b = list(map(int, b.split(' ')))
print(pairs(b,_k))
Approach 3.
#!/usr/bin/py
# Head ends here
def pairs(a, k):
d = {}
answer = 0
for i in a:
d[i] = i
for j in a:
g = j+k
if g in d:
answer +=1
return answer# Tail starts here
if __name__ == '__main__':
a = input().strip()
a = list(map(int, a.split(' ')))
_a_size=a[0]
_k=a[1]
b = input().strip()
b = list(map(int, b.split(' ')))
print(pairs(b,_k))
Solution in cpp
Approach 1.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N,k,i,c=0;
cin>>N>>k;
vector<int> v(N);
for (i = 0; i < N; i++)
{
cin>>v[i];
}
sort(v.begin(),v.end());
i=0;
for(int j = 1; j < N; j++)
{
if(v[j]-v[i]==k)
{
c++;
i++;
}
else if(v[j]-v[i]>k)
{
i++;
j--;
}
}
cout<<c;
return 0;
}
Approach 2.
#include <iostream>
#include <algorithm>
using namespace std;
int bsrch(int *a, int l, int h, int val)
{
if(h<l)
return -1;
int m = (l+h)/2;
if(a[m]==val)
return m;
if(a[m]>val)
bsrch(a,l,m-1,val);
else bsrch(a,m+1,h,val);
}
int main()
{
int n,k;
cin>>n>>k;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
sort(arr, arr+n);
int c=0,loc,t;
for(int i=0;i<n;i++){
loc = bsrch(arr,i,n-1,arr[i]+k);
if(loc!=-1){
c++; loc++;
while(loc<n && arr[loc]==arr[i]+k){
c++; loc++;
}
}
}
cout<<c<<endl;
return 0;
}
Approach 3.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, k, a[100000];
int ans = 0;
int head = 0;
void input() {
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i];
}
int findPairs(int x) {
int p = a[x];
while(true) {
if(head >= n)
return 0;
if(a[head]-p == k) {
head++;
ans++;
continue;
}
if(a[head]-p > k) {
return 0;
}
if(a[head]-p < k) {
head++;
continue;
}
}
return 0;
}
void solve() {
sort(a,a+n);
for(int i = 0; i < n; i++) {
findPairs(i);
}
cout << ans << endl;
}
int main() {
input();
solve();
return 0;
}