Dada una array arr[] que consta de N enteros, la tarea es contar el número de pares válidos (i, j) tales que arr[i] + arr[j] = arr[i] / arr[j] .
Ejemplos:
Entrada: arr[] = {-4, -3, 0, 2, 1}
Salida: 1
Explicación: El único par posible es (0, 3) que satisface la condición ( -4 + 2 = -4 / 2 (= -2) ).Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 0
Enfoque ingenuo: el enfoque simple es generar todos los pares posibles de la array dada y contar el número de pares cuya suma es igual a su división. Después de verificar, todos los pares imprimen el recuento final de posibles pares.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count all pairs (i, j)
// such that a[i] + [j] = a[i] / a[j]
int countPairs(int a[], int n)
{
// Stores total count of pairs
int count = 0;
// Generate all possible pairs
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[j] != 0
&& a[i] % a[j] == 0) {
// If a valid pair is found
if ((a[i] + a[j])
== (a[i] / a[j]))
// Increment count
count++;
}
}
}
// Return the final count
return count;
}
// Driver Code
int main()
{
int arr[] = { -4, -3, 0, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to count all pairs (i, j)
// such that a[i] + [j] = a[i] / a[j]
static int countPairs(int a[], int n)
{
// Stores total count of pairs
int count = 0;
// Generate all possible pairs
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (a[j] != 0
&& a[i] % a[j] == 0) {
// If a valid pair is found
if ((a[i] + a[j])
== (a[i] / a[j]))
// Increment count
count++;
}
}
}
// Return the final count
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { -4, -3, 0, 2, 1 };
int N = arr.length;
System.out.print(countPairs(arr, N));
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program for the above approach # Function to count all pairs (i, j) # such that a[i] + [j] = a[i] / a[j] def countPairs(a, n): # Stores total count of pairs count = 0 # Generate all possible pairs for i in range(n): for j in range(i + 1, n): if (a[j] != 0 and a[i] % a[j] == 0): # If a valid pair is found if ((a[i] + a[j]) == (a[i] // a[j])): # Increment count count += 1 # Return the final count return count # Driver Code if __name__ == '__main__': arr =[-4, -3, 0, 2, 1] N = len(arr) print (countPairs(arr, N)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG {
// Function to count all pairs (i, j)
// such that a[i] + [j] = a[i] / a[j]
static int countPairs(int[] a, int n)
{
// Stores total count of pairs
int count = 0;
// Generate all possible pairs
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (a[j] != 0
&& a[i] % a[j] == 0)
{
// If a valid pair is found
if ((a[i] + a[j])
== (a[i] / a[j]))
// Increment count
count++;
}
}
}
// Return the final count
return count;
}
// Driver code
static void Main() {
int[] arr = { -4, -3, 0, 2, 1 };
int N = arr.Length;
Console.WriteLine(countPairs(arr, N));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// JavaScript program for the above approach
// Function to count all pairs (i, j)
// such that a[i] + [j] = a[i] / a[j]
function countPairs(a, n)
{
// Stores total count of pairs
var count = 0;
// Generate all possible pairs
for (var i = 0; i < n; i++) {
for (var j = i + 1; j < n; j++) {
if (a[j] != 0
&& a[i] % a[j] == 0) {
// If a valid pair is found
if ((a[i] + a[j])
== (a[i] / a[j]))
// Increment count
count++;
}
}
}
// Return the final count
return count;
}
// Driver Code
var arr = [-4, -3, 0, 2, 1 ];
var N = arr.length;
document.write( countPairs(arr, N));
</script>
Producción:
1
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar simplificando la expresión dada y usando un mapa para contar el número de pares que satisfacen la condición simplificada a continuación:
Supongamos que X e Y son números presentes en los índices i y j , entonces la condición que debe cumplirse es:
=> X + Y = X/Y
=> X = Y 2 /(1 – Y)
Siga los pasos a continuación para resolver el problema anterior:
- Inicialice una variable, digamos count , para almacenar el recuento de todos los pares posibles que satisfagan la condición requerida.
- Inicialice un mapa para almacenar las frecuencias de los valores de la expresión anterior obtenidos para cada elemento de la array.
- Recorra la array dada usando la variable i y realice los siguientes pasos:
- Si arr[i] no es igual a 1 y 0 , entonces calcule arr[i] 2 /(1 – arr[i]) , digamos X.
- Agregue la frecuencia de X en el Mapa para contar .
- Aumenta la frecuencia de arr[i] en 1 en el Mapa .
- Después de completar los pasos anteriores, imprima el valor del conteo 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 number of pairs
// with equal sum and quotient
// from a given array
int countPairs(int a[], int n)
{
// Store the count of pairs
int count = 0;
// Stores frequencies
map<double, int> mp;
// Traverse the array
for (int i = 0; i < n; i++) {
int y = a[i];
// If y is neither 1 or 0
if (y != 0 && y != 1) {
// Evaluate x
double x = ((y * 1.0)
/ (1 - y))
* y;
// Increment count by frequency
// of x
count += mp[x];
}
// Update map
mp[y]++;
}
// Print the final count
return count;
}
// Driver Code
int main()
{
int arr[] = { -4, -3, 0, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find number of pairs
// with equal sum and quotient
// from a given array
static int countPairs(int a[], int n)
{
// Store the count of pairs
int count = 0;
// Stores frequencies
HashMap<Double, Integer> mp = new HashMap<Double, Integer>();
// Traverse the array
for (int i = 0; i < n; i++)
{
double y = a[i];
// If y is neither 1 or 0
if (y != 0 && y != 1)
{
// Evaluate x
double x = ((y * 1.0)
/ (1 - y))
* y;
// Increment count by frequency
// of x
if(mp.containsKey(x))
count += mp.get(x);
}
// Update map
if(mp.containsKey(y)){
mp.put(y, mp.get(y)+1);
}
else{
mp.put(y, 1);
}
}
// Print the final count
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { -4, -3, 0, 2, 1 };
int N = arr.length;
// Function Call
System.out.print(countPairs(arr, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to find number of pairs
# with equal sum and quotient
# from a given array
def countPairs(a, n) :
# Store the count of pairs
count = 0
# Stores frequencies
mp = {}
# Traverse the array
for i in range(n):
y = a[i]
# If y is neither 1 or 0
if (y != 0 and y != 1) :
# Evaluate x
x = (((y * 1.0)
// (1 - y))
* y)
# Increment count by frequency
# of x
count += mp.get(x, 0)
# Update map
mp[y] = mp.get(y, 0) + 1
# Print final count
return count
# Driver Code
arr = [ -4, -3, 0, 2, 1 ]
N = len(arr)
# Function Call
print(countPairs(arr, N))
# This code is contributed by susmitakundugoaldanga.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find number of pairs
// with equal sum and quotient
// from a given array
static int countPairs(int[] a, int n)
{
// Store the count of pairs
int count = 0;
// Stores frequencies
Dictionary<double, int> mp
= new Dictionary<double, int>();
// Traverse the array
for (int i = 0; i < n; i++) {
int y = a[i];
// If y is neither 1 or 0
if (y != 0 && y != 1) {
// Evaluate x
double x = ((y * 1.0) / (1 - y)) * y;
// Increment count by frequency
// of x
if (!mp.ContainsKey(x))
mp[x] = 0;
count += mp[x];
}
// Update map
if (!mp.ContainsKey(y))
mp[y] = 0;
mp[y]++;
}
// Print the final count
return count;
}
// Driver Code
public static void Main()
{
int[] arr = { -4, -3, 0, 2, 1 };
int N = arr.Length;
// Function Call
Console.Write(countPairs(arr, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to find number of pairs
// with equal sum and quotient
// from a given array
function countPairs(a, n)
{
// Store the count of pairs
let count = 0;
// Stores frequencies
let mp = new Map();
// Traverse the array
for (let i = 0; i < n; i++)
{
let y = a[i];
// If y is neither 1 or 0
if (y != 0 && y != 1)
{
// Evaluate x
let x = ((y * 1.0)
/ (1 - y))
* y;
// Increment count by frequency
// of x
if(mp.has(x))
count += mp.get(x);
}
// Update map
if(mp.has(y)){
mp.set(y, mp.get(y)+1);
}
else{
mp.set(y, 1);
}
}
// Print the final count
return count;
}
// Driver Code
let arr = [ -4, -3, 0, 2, 1 ];
let N = arr.length;
// Function Call
document.write(countPairs(arr, N));
</script>
Producción:
1
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ArifShaikh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA