Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n. Return count of such pairs.
Example k=4 and a[]={7,623,19,10,11,9,3,15}
Output should be : 6
Pairs can be:
7,11
7,3
6,10
19,23
15,19
15,11
Solution:
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX 1000000 int cmpfunc (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int main() { // Enter your code here. Read input from STDIN. Print output to STDOUT / int n,k; int *a; int count = 0; int i; scanf("%d %d", &n,&k); a = malloc(n* sizeof(*a)); for(i=0; i<n;i++){ scanf("%d",&a[i]); } qsort(a, n, sizeof(int), cmpfunc); int l = 0; int r = 0; while(r < n) { if(a[r] - a[l] == k) { count++; l++; r++; } else if(a[r] - a[l] > k) l++; else r++; } printf("%d",count); return 0; }
Time Complexity: O(NLogN)
Space Complexity: O(1)
Great article…. Thanks
import java.util.HashMap;
public class SubtractionPair {
public static void printPair(int a[],int subValue)
{
HashMap store=new HashMap();
for(int i=0;i<a.length;i++)
{
store.put(a[i],1);
}
for(int i=0;i<a.length;i++)
{
if(store.containsKey(a[i]-subValue))
{
System.out.println("("+a[i]+","+(a[i]-subValue)+")");
}
if(store.containsKey(a[i]+subValue))
{
System.out.println("("+a[i]+","+(a[i]+subValue)+")");
}
store.remove(a[i]);
}
}
public static void main(String[] args) {
int a[]={7,6,23,19,10,11,9,3,15};
printPair(a,4);
}
}
Thanks for your post
I Sorted the array before continuing. I used quick sort.This is just the idea & not the entire code . I looping the array from the end.
say if the origin list is a[]={7,623,19,10,11,9,3,15}
then after applying sort technique the list will be a[]={3,6,7,9,10,11,15,19,23}
number = 4;
Loop (End -> Start){
n = End;
if((a[n] – a[n-1]) == number){
if(a[n-2]){
if((a[n]-a[n-2])){
//pair found;
}
}
else if ((a[n] – a[n-1] ) < number){
//pair found;
}
}
n–;
}
Good day,Do you mind creating a function where you do not have to sort the array contents first
class CountPairs
{
public static void main (String[] args)
{
Integer a[] = new Integer[] {7,6,23,19,10,11,9,3,15};
int count = 0;
int k = 4;
Map map= new HashMap();
for (int i=0;i<a.length;i++) {
if (!map.containsKey(a[i]))
map.put(a[i],1);
}
for (int i=0;i<a.length;i++) {
if (map.containsKey(a[i]+k))
count++;
if (map.containsKey(a[i]-k))
count++;
map.remove(a[i]);
}
System.out.println("Pairs = "+count);
}
}
Time complexity seems like not O(nlogn). Can some one please explain this??
#include
#include
#include
using namespace std;
int main()
{
int a[8]={7,623,19,10,11,9,3,15};
int k=4,temp,n=8;
int q=0,m,o=0,w=0;
cout<<"Array is :";
for(int y=0;y<8;y++)
{
cout<<a[y]<<" ";
}
cout<<"\n\nDifference b/w pairs is:"<<k<<"\n\nPairs Are :\n\n";
while(q<n)
{
while(o<n)
{
if((a[w]-a[q]) == k)
{
cout<<a[q]<<","<<a[w]<<"\n";
}
w++;
o++;
}
q++;
w=0;
o=0;
}
getch();
}
@pawansingh It looks the complexity is not O(nlogn) correct me if I am wrong
Hey, I have one different approach let me know what you guys think of it.
(Python)Pseudo Code:
Example k=4 and a[]={7,6,23,19,10,11,9,3,15}
for i in a: #i = 7 at iter1, then 6, then 23 and so on
find = i + k # add “k” to each of them
binarySearch(a, find) # search for “find” in array a[]
Implementation using HashSet
public class SumTwoNums {
public static void main(String []args){
int diff=0;
int arr[]={2,6,4,8,9,14,16,-2,-6,0};
//Number to be checked
int num=8;
//HashSet to store array elements
HashSet hSet= new HashSet();
for(int i=0;i<arr.length;i++){
hSet.add(arr[i]);
diff=num-arr[i];
if(hSet.contains(diff) && diff!=arr[i]){
System.out.println("Pair " + arr[i] + " + " + diff + " = " + num);
}
}
}
}
//Tested with Positive and Negative numbers
/*
*Output
*Pair 6 + 2 = 8
*Pair -6 + 14 = 8
*Pair 0 + 8 = 8
*/
sort the array O(nlgn)
Fix two indices (i & j) on the start. Move one if diff is less than required else the other. If the diff is equal to required diff print the values at i and j and move both i and j.