0 like 0 dislike
428 views
Constraints :

1<=N<=1000000

1<=A[i]<=1000000000

Example :

Size of Array : 5

6 12 18 333 4

Output :  1 , Explanation : {Only 1 pair {4,6} is present in the array whose absolute difference is 2}

Note :

1)Algorithm-explanation is must .

| 428 views

2 like 0 dislike

## Approach :

For this problem we can use hashmap in java (or) maps in c++ (or) dictionary in Python .

We can keep track of frequency of each element in maps.

Our task is find (a-b) which gives 2 . Suppose ,  we are at an element 'a'  to get 'b' we should find whether a-2 exists in our array (We can do this by using the same hashmap) . If (a-2) exists , we can just add the frequency of (a-2) to our answer .

## Below is the Implementation of above approach:

```#include <bits/stdc++.h>
using namespace std;
int main() {
int n=5;
vector<int> a={6,12,18,333,4};
map<int,int> m;
for(auto x:a)
{
m[x]++;
}
int ans=0;
for(auto x:a)
{
int find=x-2;
ans+=m[find];
}
cout<<ans<<endl;

return 0;
}
```

## Input 1 :

n=5;

{    6 ,12 , 18, 333 , 4};

## Input 2:

n=10;

{6,12,18,333,4,4,8,6,-4,-2}

## output 2 :

7 ({6,4},{6,4} , {6,8}, {4,6} ,{4,6}, {8,6} , {-4,-2}  )

by Expert (540 points)
selected
1 0
Your algo is perfectly fine , one modification is that in ans we would add the product of frequencies of a and a-2 , you can check it for  your self  as every distinct number would be  accessed only once in map and every a can be paired with any one of the a-2 , hence the product of frequencies should be added. Feel free to ask if you are still having any confusion.
Anubhav Gupta
1 0
Yeah it's ok but I'm traversing on the array not on the hashmap . Please do check this.
1 like 0 dislike

### Approach :

STEP 1: - Read the inputs and create a temporary variable j and assign the value 1 to it as the index should compare freom 1.

STEP 2:-  Use a loop but don't increment everytime, increment the loop value only when the j value is at it's highest length.Becoz of this it will make the loop varaible as static and compare with every other in an array.

STEP 3: - Increase the j value if it is less the array length and assign the j value to +1 of loop varaible when the j value is at it's highest length. So, once the loop varaible increases, j value will be +1 of loop varaible.

STEP 4 :- Increase the count if the diference is equal to 2.

Code:-

```using System;
using System.Linq;
using System.Collections.Generic;

public class Test
{
public static void Main()
{

int j=1,count=0;
int[] arr={6,12,18,333,4};
for(int i=0;i<arr.Length;)
{
if(j<arr.Length)
{
if(Math.Abs(arr[i]-arr[j])==2)
count++;
j++;

}
if(j==arr.Length)
{
j=i+1;
i++;
}
}
Console.WriteLine(count);
}
}```
by Expert (980 points)