Count number of pairs (i, j) such that a[j]−a[i] = j−i

Given an array of distinct positive integers arr[] of length N, the task is to count all the number of pairs of indices (i , j) such that a[j]−a[i] = j−i given that i<j always.

Examples:

Input: 2 3 1 4 
Output: 2

Input: 1 2 3 4
Output: 6

Approach-1: Simple Brute Force:
We will use 2 for loop to iterate over the array and will check the difference if same then we will count that.
Implementation of the above approach given below.

#include<bits/stdc++.h>
using namespace std;
using ll= long long;

void solve(ll arr[],ll n){
    	    
  		ll count =0;
  
        for(ll i=0;i<n;i++){
            for(ll j=i+1;j<n;j++){
                if(j-i==arr[j]-arr[i]){
                    count++;
                }
            }
        }
        cout<<count<<"\n";
}

int main(){
        ll arr[] = {1,2,3,4};
        ll n = sizeof(arr) / sizeof(arr[0]);
        solve(arr,n);
    return 0;
}

Output:

Time complexity : O(n^2)

Approach-2: Using Map
We can do the same problem using map approach as we can see from this problem that

a[j]−a[i] = j−i  is also equal to a[j] - j = a[i] - i

So simply we will modify array into a[i]-i then we will iterate to n and check for a condition if true then we will insert them into map else we will count the frequency.
This will be much optimized approach Implementation of the above approach given below:

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define endl "\n"

void solve(ll v[], ll n) {

  for (ll i = 0; i < n; i++) {
    v[i] -= i;
  }

  map < ll, ll > mp;

  ll count = 0;

  for (ll i = 0; i < n; i++) {
    if (mp.count(v[i]) == 0) {
      mp.insert({
        v[i],
        1
      });
    } else {
      ll val = mp[v[i]];
      count += (val);
      mp[v[i]]++;
    }
  }
  cout << count << endl;

}
int main() {

  ll v[] = {1,2,3,4};
  ll n = sizeof(v) / sizeof(v[0]);
  solve(v, n);

  return 0;
}

Output:

Time complexity : O(n)