How to calculate the total number of pairs (i,j) in an array such that abs(a[i]-a[j]) = 2 in O(N) ?

Question

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 .

2)Adding code is optional .

Answer 1

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};

output : 1   ({6-4=2})

---

---

---

---

---

---

---

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}  )

---

 

Comments

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

---

Yeah it's ok but I'm traversing on the array not on the hashmap . Please do check this.

Answer 2

#Time Complexity - O(N)

Language - C#

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);
    }
}