Dada una array arr[] de N enteros tanto positivos como negativos, nuestra tarea es encontrar el número de pares desordenados (x, y) que satisfacen las ecuaciones dadas:
- | x | > = min(| x – y|, | x + y|)
- | y | < = máx(| x – y|, | x + y|)
Ejemplos:
Entrada: arr[] = [ 2, 5, -3 ]
Salida: 2
Explicación:
Los posibles pares no ordenados son (5, -3) y (2, -3). (2, 5) no se cuenta porque no cumple las condiciones.Entrada: arr[] = [ 3, 6 ]
Salida: 1
Explicación:
El par [3, 6] satisface la condición. Por lo tanto, la salida es 1.
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, el método ingenuo es atravesar todos los pares posibles y no contar los pares desordenados que satisfacen estas condiciones. Pero este método es costoso y requiere más tiempo, lo que puede optimizarse aún más.
Tiempo Complejidad: O(N 2 )
Espacio auxiliar : O(1)
Enfoque eficiente:
para optimizar el método anterior, la idea principal es ordenar la array y luego aplicar la búsqueda binaria para encontrar el límite correcto para cada índice de la array. Tenemos que observar que si cambiamos x a – x , entonces los valores de |x| y |y| permanece igual, mientras que |x – y| y |x + y| intercambiará valores. Esto significa que el par {x, y} funciona si y solo si funciona {-x, y}. Del mismo modo, podemos cambiar el signo de y. Esto significa que podemos reemplazar x e y por sus valores absolutos , y el par original funciona si y solo si funciona el nuevo.
Si x > = 0 y y > = 0 entonces la condición se convierte en |x – y | < = x, y < = x + y . El límite superior siempre se cumple, mientras que el límite inferior es equivalente a x < = 2 * y y y < = 2 * x
Entonces el problema se reduce a contar el número de pares {x, y} con |x| <= 2|año| y |y| <= 2|x| . Para resolver esto, tomamos los valores absolutos de todos los A[i] y ordenamos el arreglo que es el número de pares (l, r) con l < r y a[r] < = 2 * a[l]. Para cada l fijo, calculamos el r más grande que satisface esta condición, y simplemente lo sumamos con la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the number of
// unordered pairs (x, y) which satisfy
// the given equation for the array
#include <bits/stdc++.h>
using namespace std;
// Return the number of unordered
// pairs satisfying the conditions
int numPairs(int a[], int n)
{
int ans, i, index;
// ans stores the number
// of unordered pairs
ans = 0;
// Making each value of
// array to positive
for (i = 0; i < n; i++)
a[i] = abs(a[i]);
// Sort the array
sort(a, a + n);
// For each index calculating
// the right boundary for
// the unordered pairs
for (i = 0; i < n; i++) {
index = upper_bound(
a,
a + n,
2 * a[i])
- a;
ans += index - i - 1;
}
// Return the final result
return ans;
}
// Driver code
int main()
{
int a[] = { 3, 6 };
int n = sizeof(a)
/ sizeof(a[0]);
cout << numPairs(a, n)
<< endl;
return 0;
}
Java
// Java Program to find the number of
// unordered pairs (x, y) which satisfy
// the given equation for the array
import java.util.Arrays;
class GFG{
// Return the number of unordered
// pairs satisfying the conditions
static int numPairs(int a[], int n)
{
int ans, i, index;
// ans stores the number
// of unordered pairs
ans = 0;
// Making each value of
// array to positive
for (i = 0; i < n; i++)
a[i] = Math.abs(a[i]);
// Sort the array
Arrays.sort(a);
// For each index calculating
// the right boundary for
// the unordered pairs
for (i = 0; i < n; i++)
{
index = 2;
ans += index - i - 1;
}
// Return the final result
return ans;
}
// Driver code
public static void main(String []args)
{
int a[] = new int[]{ 3, 6 };
int n = a.length;
System.out.println(numPairs(a, n));
}
}
// This code is contributed by rock_cool
Python3
# Python3 program to find the number of # unordered pairs (x, y) which satisfy # the given equation for the array # Return the number of unordered # pairs satisfying the conditions def numPairs(a, n): # ans stores the number # of unordered pairs ans = 0 # Making each value of array # to positive for i in range(n): a[i] = abs(a[i]) # Sort the array a.sort() # For each index calculating # the right boundary for # the unordered pairs for i in range(n): index = 0 for j in range(i + 1, n): if (2 * a[i] >= a[j - 1] and 2 * a[i] < a[j]): index = j if index == 0: index = n ans += index - i - 1 # Return the final result return ans # Driver code a = [ 3, 6 ] n = len(a) print(numPairs(a, n)) # This code is contributed by avanitrachhadiya2155
C#
// C# Program to find the number of
// unordered pairs (x, y) which satisfy
// the given equation for the array
using System;
class GFG{
// Return the number of unordered
// pairs satisfying the conditions
static int numPairs(int []a, int n)
{
int ans, i, index;
// ans stores the number
// of unordered pairs
ans = 0;
// Making each value of
// array to positive
for (i = 0; i < n; i++)
a[i] = Math.Abs(a[i]);
// Sort the array
Array.Sort(a);
// For each index calculating
// the right boundary for
// the unordered pairs
for (i = 0; i < n; i++)
{
index = 2;
ans += index - i - 1;
}
// Return the final result
return ans;
}
// Driver code
public static void Main()
{
int []a = new int[]{ 3, 6 };
int n = a.Length;
Console.Write(numPairs(a, n));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript Program to find the number of
// unordered pairs (x, y) which satisfy
// the given equation for the array
// Return the number of unordered
// pairs satisfying the conditions
function numPairs(a, n)
{
let ans, i, index;
// ans stores the number
// of unordered pairs
ans = 0;
// Making each value of
// array to positive
for (i = 0; i < n; i++)
a[i] = Math.abs(a[i]);
// Sort the array
a.sort();
// For each index calculating
// the right boundary for
// the unordered pairs
for (i = 0; i < n; i++)
{
index = 2;
ans += index - i - 1;
}
// Return the final result
return ans;
}
let a = [ 3, 6 ];
let n = a.length;
document.write(numPairs(a, n));
</script>
1
Complejidad de Tiempo: O(n * log n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ujjwalmittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA