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:
6
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:
6
Time complexity : O(n)