Cuente los pares en una array dada que tenga la suma del índice y el valor en ese índice igual

Dada una array arr[] que contiene enteros positivos, cuente el número total de pares para los cuales arr[i]+i = arr[j]+j tal que 0≤i<j≤n-1 .

Ejemplos :

Entrada: arr[] = { 6, 1, 4, 3 }
Salida: 3
Explicación: Los elementos en el índice 0, 2, 3 tienen el mismo valor de a[i]+i que todos suman 6 {(6+0) , (4+2), (3+3)}.

Entrada: arr[] = { 8, 7, 6, 5, 4, 3, 2, 1 }
Salida: 28

Enfoque ingenuo: el enfoque de fuerza bruta se implementa iterando dos bucles y contando todos los pares que siguen a arr[i]+i = arr[j]+j . 

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

// C++ program to find Count the pair of
// elements in  an array such that
// arr[i]+i=arr[j]+j
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// total count of pairs
int count(int arr[], int n)
{
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((arr[i] + i) == (arr[j] + j)) {
                ans++;
            }
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 6, 1, 4, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << count(arr, N);
    return 0;
}

// Java program to find Count the pair of
// elements in  an array such that
// arr[i]+i=arr[j]+j
import java.io.*;
class GFG
{
 
  // Function to return the
  // total count of pairs
  static int count(int arr[], int n)
  {
    int ans = 0;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if ((arr[i] + i) == (arr[j] + j)) {
          ans++;
        }
      }
    }
    return ans;
  }
 
  // Driver code
  public static void main (String[] args) {
    int arr[] = { 6, 1, 4, 3 };
    int N = arr.length;
    System.out.println(count(arr, N));
  }
}
 
// This code is contributed by hrithikgarg03188.

# python3 program to find Count the pair of
# elements in an array such that
# arr[i]+i=arr[j]+j
 
# Function to return the
# total count of pairs
def count(arr, n):
 
    ans = 0
    for i in range(0, n):
        for j in range(i + 1, n):
            if ((arr[i] + i) == (arr[j] + j)):
                ans += 1
 
    return ans
   
# Driver code
if __name__ == "__main__":
 
    arr = [6, 1, 4, 3]
    N = len(arr)
    print(count(arr, N))
 
# This code is contributed by rakeshsahni

// C# program to find Count the pair of
// elements in  an array such that
// arr[i]+i=arr[j]+j
using System;
class GFG {
 
    // Function to return the
    // total count of pairs
    static int count(int[] arr, int n)
    {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((arr[i] + i) == (arr[j] + j)) {
                    ans++;
                }
            }
        }
        return ans;
    }
 
    // Driver code
    public static int Main()
    {
        int[] arr = new int[] { 6, 1, 4, 3 };
        int N = arr.Length;
        Console.WriteLine(count(arr, N));
        return 0;
    }
}
 
// This code is contributed by Taranpreet

<script>
// Javascript program to find Count the pair of
// elements in  an array such that
// arr[i]+i=arr[j]+j
 
// Function to return the
// total count of pairs
function count(arr, n)
{
    let ans = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if ((arr[i] + i) == (arr[j] + j)) {
                ans++;
            }
        }
    }
    return ans;
}
 
// Driver code
let arr = [ 6, 1, 4, 3 ];
let N = arr.length;
document.write(count(arr, N));
 
// This code is contributed by Samim Hossain Mondal.
</script>

3

Complejidad temporal: O(N^2)
Espacio auxiliar: O(1)

Enfoque eficiente: este problema se puede resolver de manera eficiente utilizando unordered_map en C++. Esto se hace para almacenar el conteo de elementos similares en un tiempo promedio de O(1). Luego, para cada elemento similar, podemos usar el conteo de ese elemento para evaluar el número total de pares, como 

Para x artículos similares => el número de pares será x*(x-1)/2

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

// C++ program to find Count the pair of
// elements in  an array such that
// arr[i]+i=arr[j]+j
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// total count of pairs
int count(int arr[], int n)
{
    // Modifying the array by storing
    // a[i]+i at all instances
    for (int i = 0; i < n; i++) {
        arr[i] = arr[i] + i;
    }
 
    // Using unordered_map to store
    // the elements
    unordered_map<int, int> mp;
 
    for (int i = 0; i < n; i++) {
        mp[arr[i]]++;
    }
 
    // Now for each elements in unordered_map
    // we are using the count of that element
    // to determine the number of pairs possible
    int ans = 0;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        int val = it->second;
        ans += (val * (val - 1)) / 2;
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 8, 7, 6, 5, 4, 3, 2, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << count(arr, N);
    return 0;
}

/*package whatever //do not write package name here */
 
// Java program to find Count the pair of
// elements in an array such that
// arr[i]+i=arr[j]+j
import java.io.*;
import java.util.*;
 
class GFG {
 
// Function to return the
// total count of pairs
static int count(int arr[], int n)
{
   
    // Modifying the array by storing
    // a[i]+i at all instances
    for (int i = 0; i < n; i++) {
        arr[i] = arr[i] + i;
    }
 
    // Using unordered_map to store
    // the elements
    HashMap<Integer,Integer>mp = new HashMap<Integer,Integer>();
 
    for (int i = 0; i < n; i++) {
        if(mp.containsKey(arr[i])){
            mp.put(arr[i], mp.get(arr[i])+1);
        }
        else mp.put(arr[i],1);
    }
 
    // Now for each elements in unordered_map
    // we are using the count of that element
    // to determine the number of pairs possible
    int ans = 0;
    for(int it : mp.keySet()){
        ans += (mp.get(it)*(mp.get(it)-1))/2;
    }
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 8, 7, 6, 5, 4, 3, 2, 1 };
    int N = arr.length;
    System.out.println(count(arr, N));
}
}
 
// This code is contributed by shinjanpatra

# Python program to find Count the pair of
# elements in  an array such that
# arr[i]+i=arr[j]+j
 
 
# Function to return the
# total count of pairs
def count(arr, n):
 
    # Modifying the array by storing
    # a[i]+i at all instances
    for i in range(n):
        arr[i] = arr[i] + i
 
    # Using unordered_map to store
    # the elements
    mp = {}
 
    for i in range(n):
        if(arr[i] in mp):
            mp[arr[i]] = mp[arr[i]]+1
        else:
            mp[arr[i]] = 1
 
    # Now for each elements in unordered_map
    # we are using the count of that element
    # to determine the number of pairs possible
    ans = 0
    for val in mp.values():
        ans += (val * (val - 1)) // 2
     
    return ans
 
# Driver code
 
arr = [ 8, 7, 6, 5, 4, 3, 2, 1 ]
N = len(arr)
print(count(arr, N))
 
# This code is contributed by shinjanpatra

// C# program to find Count the pair of
// elements in an array such that
// arr[i]+i=arr[j]+j
using System;
using System.Collections.Generic;
 
class GFG {
 
// Function to return the
// total count of pairs
static int count(int[] arr, int n)
{
 
    // Modifying the array by storing
    // a[i]+i at all instances
    for (int i = 0; i < n; i++) {
        arr[i] = arr[i] + i;
    }
 
    // Using unordered_map to store
    // the elements
    Dictionary<int, int> mp = new Dictionary<int, int>();
 
    for (int i = 0; i < n; i++) {
        if(mp.ContainsKey(arr[i])){
            mp[arr[i]] =  mp[arr[i]] + 1;
        }
        else mp.Add(arr[i], 1);
    }
 
    // Now for each elements in unordered_map
    // we are using the count of that element
    // to determine the number of pairs possible
    int ans = 0;
    foreach(KeyValuePair<int, int> it in mp){
        ans += (it.Value*(it.Value-1))/2;
    }
    return ans;
}
 
// Driver code
public static int Main()
    {
        int[] arr = new int[] { 8, 7, 6, 5, 4, 3, 2, 1 };
        int N = arr.Length;
        Console.WriteLine(count(arr, N));
        return 0;
    }
}
 
// This code is contributed by Aman Kumar

<script>
 
// JavaScript program to find Count the pair of
// elements in  an array such that
// arr[i]+i=arr[j]+j
 
// Function to return the
// total count of pairs
function count(arr, n)
{
 
    // Modifying the array by storing
    // a[i]+i at all instances
    for (let i = 0; i < n; i++) {
        arr[i] = arr[i] + i;
    }
 
    // Using unordered_map to store
    // the elements
    let mp = new Map();
 
    for (let i = 0; i < n; i++) {
        if(mp.has(arr[i])){
            mp.set(arr[i], mp.get(arr[i]) + 1);
        }
        else mp.set(arr[i], 1);
    }
 
    // Now for each elements in unordered_map
    // we are using the count of that element
    // to determine the number of pairs possible
    let ans = 0;
    for (let [key,val] of mp){
        ans += Math.floor((val * (val - 1)) / 2);
    }
    return ans;
}
 
// Driver code
let arr = [ 8, 7, 6, 5, 4, 3, 2, 1 ];
let N = arr.length;
document.write(count(arr, N));
 
// This code is contributed by shinjanpatra
 
</script>

28

Complejidad temporal: O(N)
Espacio auxiliar: O(N)