Dada una array arr[] que consta de N enteros, la tarea es encontrar el número de pares (i, j) cuya suma de índices es la misma que la suma de elementos en los índices.
Ejemplos:
Entrada: arr[] = {0, 1, 7, 4, 3, 2}
Salida: 1
Explicación: Solo existe un par que satisface la condición {(0, 1)}.Entrada: arr[] = {1, 6, 2, 4, 5, 6}
Salida: 0
Enfoque ingenuo: el enfoque simple para resolver el problema dado es generar todos los pares posibles de la array dada y si la suma de cualquier par es igual a la suma de sus índices, entonces cuente este par. Después de verificar todos los pares, imprima el conteo total obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find all possible pairs
// of the given array such that the sum
// of arr[i] + arr[j] is i + j
void countPairs(int arr[], int N)
{
// Stores the total count of pairs
int answer = 0;
// Iterate over the range
for (int i = 0; i < N; i++) {
// Iterate over the range
for (int j = i + 1; j < N; j++) {
if (arr[i] + arr[j] == i + j) {
answer++;
}
}
}
// Print the total count
cout << answer;
}
// Driver Code
int main()
{
int arr[] = { 0, 1, 2, 3, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find all possible pairs
// of the given array such that the sum
// of arr[i] + arr[j] is i + j
public static void countPairs(int arr[], int N)
{
// Stores the total count of pairs
int answer = 0;
// Iterate over the range
for(int i = 0; i < N; i++)
{
// Iterate over the range
for(int j = i + 1; j < N; j++)
{
if (arr[i] + arr[j] == i + j)
{
answer++;
}
}
}
// Print the total count
System.out.println(answer);
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 0, 1, 2, 3, 4, 5 };
int N = arr.length;
countPairs(arr, N);
}
}
// This code is contributed by gfgking
Python3
# Python3 program for the above approach # Function to find all possible pairs # of the given array such that the sum # of arr[i] + arr[j] is i + j def countPairs(arr, N): # Stores the total count of pairs answer = 0 # Iterate over the range for i in range(N): # Iterate over the range for j in range(i + 1, N): if arr[i] + arr[j] == i + j: answer += 1 # Print the total count print(answer) # Driver code arr = [ 0, 1, 2, 3, 4, 5 ] N = len(arr) countPairs(arr, N) # This code is contributed by Parth Manchanda
C#
// C# program for the above approach
using System;
class GFG{
// Function to find all possible pairs
// of the given array such that the sum
// of arr[i] + arr[j] is i + j
static void countPairs(int[] arr, int N)
{
// Stores the total count of pairs
int answer = 0;
// Iterate over the range
for(int i = 0; i < N; i++)
{
// Iterate over the range
for(int j = i + 1; j < N; j++)
{
if (arr[i] + arr[j] == i + j)
{
answer++;
}
}
}
// Print the total count
Console.Write(answer);
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 0, 1, 2, 3, 4, 5 };
int N = arr.Length;
countPairs(arr, N);
}
}
// This code is contributed by target_2
Javascript
<script>
// JavaScript program for the above approach
// Function to find all possible pairs
// of the given array such that the sum
// of arr[i] + arr[j] is i + j
function countPairs(arr, N)
{
// Stores the total count of pairs
let answer = 0;
// Iterate over the range
for (let i = 0; i < N; i++) {
// Iterate over the range
for (let j = i + 1; j < N; j++) {
if (arr[i] + arr[j] == i + j) {
answer++;
}
}
}
// Print the total count
document.write(answer);
}
// Driver Code
let arr = [0, 1, 2, 3, 4, 5];
let N = arr.length;
countPairs(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción:
15
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de un mapa desordenado para almacenar el recuento de elementos que tienen un valor (arr[i] – i) en la array arr[] . Siga los pasos a continuación para resolver el problema:
- Inicialice la variable, diga respuesta como 0 para almacenar el recuento de pares en la array arr[].
- Inicialice un mapa desordenado mp[] para almacenar la frecuencia de un elemento en la array arr[] que tenga valor (arr[i] – i) .
- Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
- Inicialice la variable keyValue como el valor de (arr[i] – i) .
- Aumente el valor de keyValue en el mapa desordenado mp[] en 1 .
- Iterar sobre el mapa desordenado mp[] usando la variable i y realizar los siguientes pasos:
- Inicialice el tamaño de la variable como i.segundo el valor del mapa desordenado mp[] .
- Agregue el valor de tamaño*(tamaño – 1)/2 a la variable respuesta .
- Después de realizar los pasos anteriores, imprima el valor de la respuesta como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find all possible pairs
// of the given array such that the sum
// of arr[i] + arr[j] is i + j
void countPairs(int arr[], int N)
{
// Stores the total count of pairs
int answer = 0;
unordered_map<int, int> mp;
// Iterate over the range [0, N]
for (int i = 0; i < N; i++) {
int keyValue = arr[i] - i;
mp[keyValue]++;
}
// Iterate over the range [0, N]
for (auto i : mp) {
int size = i.second;
answer += (size * (size - 1)) / 2;
}
// Print the answer
cout << answer;
}
// Driver Code
int main()
{
int arr[] = { 0, 1, 2, 3, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
countPairs(arr, N);
return 0;
}
Java
/*package whatever //do not write package name here */
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find all possible pairs
// of the given array such that the sum
// of arr[i] + arr[j] is i + j
public static void countPairs(int[] arr, int n)
{
// Stores the total count of pairs
int answer = 0;
HashMap<Integer, Integer> mp
= new HashMap<Integer, Integer>();
// Iterate over the range [0, N]
for (int i = 0; i < n; i++) {
int value = arr[i] - i;
if (mp.containsKey(value)) {
mp.put(value, mp.get(value) + 1);
}
else {
mp.put(value, 1);
}
}
// Iterate over the range [0, N]
for (Map.Entry<Integer, Integer> map :
mp.entrySet()) {
int temp = map.getValue();
answer += temp * (temp - 1) / 2;
}
// Print the answer
System.out.println(answer);
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 0, 1, 2, 3, 4, 5 };
int n = 6;
countPairs(arr, n);
}
}
// This code is contributed by maddler.
Python3
# Python3 program for the above approach
# Function to find all possible pairs
# of the given array such that the sum
# of arr[i] + arr[j] is i + j
def countPairs(arr, N):
# Stores the total count of pairs
answer = 0
mp = {}
# Iterate over the range [0, N]
for i in range(N):
keyValue = arr[i] - i
if keyValue in mp.keys():
mp[keyValue] += 1
else:
mp[keyValue] = 1
# Iterate over the range [0, N]
for size in mp.values():
answer += (size * (size - 1)) // 2
print(answer)
# Driver code
arr = [ 0, 1, 2, 3, 4, 5 ]
N = len(arr)
countPairs(arr, N)
# This code is contributed by Parth Manchanda
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find all possible pairs
// of the given array such that the sum
// of arr[i] + arr[j] is i + j
static void countPairs(int []arr, int N)
{
// Stores the total count of pairs
int answer = 0;
Dictionary<int,int> mp = new Dictionary<int,int>();
// Iterate over the range [0, N]
for (int i = 0; i < N; i++) {
int keyValue = arr[i] - i;
if(mp.ContainsKey(keyValue))
mp[keyValue]++;
else
mp.Add(keyValue,1);
}
// Iterate over the range [0, N]
foreach(KeyValuePair<int,int> entry in mp)
{
int size = entry.Value;
answer += (size * (size - 1)) / 2;
}
// Print the answer
Console.Write(answer);
}
// Driver Code
public static void Main()
{
int []arr = {0, 1, 2, 3, 4, 5 };
int N = arr.Length;
countPairs(arr, N);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to find all possible pairs
// of the given array such that the sum
// of arr[i] + arr[j] is i + j
function countPairs(arr, N) {
// Stores the total count of pairs
let answer = 0;
let mp = new Map();
// Iterate over the range [0, N]
for (let i = 0; i < N; i++) {
let keyValue = arr[i] - i;
if (mp.has(keyValue)) {
mp.set(keyValue, mp.get(keyValue) + 1);
} else {
mp.set(keyValue, 1);
}
}
// Iterate over the range [0, N]
for (let i of mp) {
let size = i[1];
answer += (size * (size - 1)) / 2;
}
// Print the answer
document.write(answer);
}
// Driver Code
let arr = [0, 1, 2, 3, 4, 5];
let N = arr.length;
countPairs(arr, N);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
15
Complejidad temporal: O(N)
Espacio auxiliar: O(N)