Dada una array arr[] de tamaño N , la tarea es contar el número de pares (i, j) posibles de la array tal que arr[j] * i = arr[i] * j , donde 1 ≤ i < j ≤ n
Ejemplos:
Entrada: arr[] = {1, 3, 5, 6, 5}
Salida: 2
Explicación:
Par (1, 5) cumple la condición, ya que arr[1] * 5 = arr[5] * 1.
Par (2 , 4) satisface la condición, ya que arr[2] * 4 = arr[4] * 2.
Por lo tanto, el número total de pares que satisfacen la condición dada es 2.Entrada: arr[] = {2, 1, 3}
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares posibles de la array y verificar para cada par, si la condición dada satisface o no. Aumente el recuento de los pares para los que se cumple la condición. Finalmente, imprima el conteo de todos esos pares.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en la reorganización de la ecuación dada arr[i] * j = arr[j] * i a arr[i] / i = arr[j] / j .
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos count , para almacenar el recuento total de pares que satisfacen las condiciones dadas.
- Inicialice un mapa desordenado , digamos mp, para contar la frecuencia de los valores arr[i] / i .
- Recorra la array arr[] y actualice las frecuencias de arr[i]/i en el Mapa .
- Imprime el conteo como la respuesta.
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 count pairs from an
// array satisfying given conditions
void countPairs(int arr[], int N)
{
// Stores the total
// count of pairs
int count = 0;
// Stores count of a[i] / i
unordered_map<double, int> mp;
// Traverse the array
for (int i = 0; i < N; i++) {
double val = 1.0 * arr[i];
double idx = 1.0 * (i + 1);
// Updating count
count += mp[val / idx];
// Update frequency
// in the Map
mp[val / idx]++;
}
// Print count of pairs
cout << count;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 3, 5, 6, 5 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Function call to count pairs
// satisfying given conditions
countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count pairs from an
// array satisfying given conditions
static void countPairs(int []arr, int N)
{
// Stores the total
// count of pairs
int count = 0;
// Stores count of a[i]/i
Map<Double, Integer> mp
= new HashMap<Double, Integer>();
// Traverse the array
for(int i = 0; i < N; i++)
{
Double val = 1.0 * arr[i];
Double idx = 1.0 * (i + 1);
// Updating count
if (mp.containsKey(val / idx))
count += mp.get(val/idx);
// Update frequency
// in the Map
if (mp.containsKey(val / idx))
mp.put(val / idx, mp.getOrDefault(val / idx, 0) + 1);
else
mp.put(val/idx, 1);
}
// Print count of pairs
System.out.print(count);
}
// Driver Code
public static void main(String args[])
{
// Given array
int []arr = { 1, 3, 5, 6, 5 };
// Size of the array
int N = arr.length;
// Function call to count pairs
// satisfying given conditions
countPairs(arr, N);
}
}
// This code is contributed by ipg2016107.
Python3
# Python3 program for the above approach from collections import defaultdict # Function to count pairs from an # array satisfying given conditions def countPairs(arr, N): # Stores the total # count of pairs count = 0 # Stores count of a[i] / i mp = defaultdict(int) # Traverse the array for i in range(N): val = 1.0 * arr[i] idx = 1.0 * (i + 1) # Updating count count += mp[val / idx] # Update frequency # in the Map mp[val / idx] += 1 # Print count of pairs print(count) # Driver Code if __name__ == "__main__": # Given array arr = [1, 3, 5, 6, 5] # Size of the array N = len(arr) # Function call to count pairs # satisfying given conditions countPairs(arr, N) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count pairs from an
// array satisfying given conditions
static void countPairs(int []arr, int N)
{
// Stores the total
// count of pairs
int count = 0;
// Stores count of a[i]/i
Dictionary<double,
int> mp = new Dictionary<double,
int>();
// Traverse the array
for(int i = 0; i < N; i++)
{
double val = 1.0 * arr[i];
double idx = 1.0 * (i + 1);
// Updating count
if (mp.ContainsKey(val / idx))
count += mp[val/idx];
// Update frequency
// in the Map
if (mp.ContainsKey(val / idx))
mp[val / idx]++;
else
mp[val/idx] = 1;
}
// Print count of pairs
Console.WriteLine(count);
}
// Driver Code
public static void Main()
{
// Given array
int []arr = { 1, 3, 5, 6, 5 };
// Size of the array
int N = arr.Length;
// Function call to count pairs
// satisfying given conditions
countPairs(arr, N);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
// Function to count pairs from an
// array satisfying given conditions
function countPairs(arr, N)
{
// Stores the total
// count of pairs
var count = 0;
// Stores count of a[i] / i
var mp = new Map();
// Traverse the array
for (var i = 0; i < N; i++) {
var val = 1.0 * arr[i];
var idx = 1.0 * (i + 1);
// Updating count
count += mp.has(val/idx)?mp.get(val/idx):0
// Update frequency
// in the Map
if(mp.has(val/idx))
mp.set(val/idx, mp.get(val/idx)+1)
else
mp.set(val/idx, 1)
}
// Print count of pairs
document.write( count);
}
// Driver Code
// Given array
var arr = [1, 3, 5, 6, 5];
// Size of the array
var N = arr.length;
// Function call to count pairs
// satisfying given conditions
countPairs(arr, N);
// This code is contributed by itsok.
</script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shubhampokhriyal2018 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA