Recuento de pares (arr[i], arr[j]) tales que arr[i] + j y arr[j] + i son iguales

Dada una array arr[] , la tarea es contar los pares i, j tales que, i < j y arr[i] + j = arr[j] + i .

Ejemplos: 

Entrada: arr[] = {4, 1, 2, 3}
Salida: 3
Explicación: En total, tres pares cumplen la condición dada: {1, 2}, {2, 3} y {1, 3}.
Entonces, la respuesta final es 3. 

Entrada: arr[] = {1, 5, 6}
Salida: 1

Enfoque ingenuo: el enfoque ingenuo para resolver este problema es verificar todos y cada uno de los pares de la array para la condición dada y contar esos pares.

Complejidad de tiempo: O(N), donde N es el tamaño de arr[]. 
Espacio Auxiliar: O(1).

Enfoque eficiente: este problema se puede resolver mediante el uso de hashmaps. Al principio, podemos torcer la condición que se nos da, podemos cambiar arr[j] + i= arr[i]+ j a arr[j] – j = arr[i] – i, lo que significa dos números diferentes teniendo la misma diferencia en su valor e índice. Eso lo hace fácil. Ahora siga los pasos a continuación para resolver el problema dado. 

• Cree un mapa mp y una variable, digamos, ans = 0 , para almacenar la respuesta.
• Recorre toda la array arr[] con say i.
  • Para cada elemento, encontraremos la diferencia en su valor e índice, simplemente a[i] – i .
  • Si hay algún valor presente en el mapa, eso significa que hay otros números con el mismo valor, por lo que agregaremos esas frecuencias a la respuesta.
  • Aumente el valor de mp[a[i] – i] .
• Devuelve ans como respuesta final.

A continuación se muestra la implementación del enfoque anterior:

#include <bits/stdc++.h>
using namespace std;
 
// Function to count pairs with given properties
int solve(int N, int arr[])
{
    // Map for the storing the frequency
    // of a given difference
    map<int, int> mp;
 
    // Variable to store the final ans
    int ans = 0;
 
    // Traverse the array and update mp
    for (int i = 0; i < N; i++) {
        ans += mp[arr[i] - i];
        mp[arr[i] - i]++;
    }
 
    // Return the final result
    return ans;
}
 
int main()
{
    int N = 4;
    int arr[] = { 4, 1, 2, 3 };
 
    // Print the result
    cout << solve(N, arr);
    return 0;
}

import java.util.*;
 
class GFG{
 
// Function to count pairs with given properties
static int solve(int N, int arr[])
{
   
    // Map for the storing the frequency
    // of a given difference
    HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
 
    // Variable to store the final ans
    int ans = 0;
 
    // Traverse the array and update mp
    for (int i = 0; i < N; i++) {
        if(mp.containsKey(arr[i]-i)){
            ans+=mp.get(arr[i]-i);
            mp.put(arr[i]-i, mp.get(arr[i]-i)+1);
        }
        else{
            mp.put(arr[i]-i, 1);
        }
    }
 
    // Return the final result
    return ans;
}
 
public static void main(String[] args)
{
    int N = 4;
    int arr[] = { 4, 1, 2, 3 };
 
    // Print the result
    System.out.print(solve(N, arr));
}
}
 
// This code is contributed by shikhasingrajput

# Python Program to implement
# the above approach
 
# Function to count pairs with given properties
def solve(N, arr):
 
    # Map for the storing the frequency
    # of a given difference
    mp = dict()
 
    # Variable to store the final ans
    ans = 0
 
    # Traverse the array and update mp
    for i in range(N):
 
        if ((arr[i] - i) not in mp):
            mp[arr[i] - i] = 0
 
        ans += mp[arr[i] - i]
        mp[arr[i] - i] = mp[arr[i] - i] + 1
 
    # Return the final result
    return ans
 
N = 4
arr = [4, 1, 2, 3]
 
# Print the result
print(solve(N, arr))
 
# This code is contributed by Saurabh Jaiswal

using System;
using System.Collections.Generic;
 
public class GFG{
 
// Function to count pairs with given properties
static int solve(int N, int []arr)
{
   
    // Map for the storing the frequency
    // of a given difference
    Dictionary<int,int> mp = new Dictionary<int,int>();
 
    // Variable to store the readonly ans
    int ans = 0;
 
    // Traverse the array and update mp
    for (int i = 0; i < N; i++) {
        if(mp.ContainsKey(arr[i]-i)){
            ans+=mp[arr[i]-i];
            mp[arr[i]-i]= mp[arr[i]-i]+1;
        }
        else{
            mp.Add(arr[i]-i, 1);
        }
    }
 
    // Return the readonly result
    return ans;
}
 
public static void Main(String[] args)
{
    int N = 4;
    int []arr = { 4, 1, 2, 3 };
 
    // Print the result
    Console.Write(solve(N, arr));
}
}
 
// This code is contributed by 29AjayKumar

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to count pairs with given properties
        function solve(N, arr)
        {
         
            // Map for the storing the frequency
            // of a given difference
            let mp = new Map();
 
            // Variable to store the final ans
            let ans = 0;
 
            // Traverse the array and update mp
            for (let i = 0; i < N; i++) {
 
                if (mp.has(arr[i] - i) == false) {
                    mp.set(arr[i] - i, 0)
                }
                ans += mp.get(arr[i] - i);
                mp.set(arr[i] - i, mp.get(arr[i] - i) + 1);
            }
 
            // Return the final result
            return ans;
        }
 
        let N = 4;
        let arr = [4, 1, 2, 3];
 
        // Print the result
        document.write(solve(N, arr));
 
    // This code is contributed by Potta Lokesh
    </script>

3

Complejidad de tiempo:  , donde N es el tamaño de la array.

Espacio auxiliar: O(N), donde N es el tamaño de la array.