Dada una array arr[] de tamaño N , la tarea es contar el número de pares (arr[i], arr[j]) tales que |arr[i]| y |arr[j]| se encuentra entre |arr[i] – arr[j]| y |arr[i] + arr[j]| .
Ejemplos:
Entrada: arr[] = {1, 3, 5, 7}
Salida: 2
Explicación:
El par (arr[1], arr[2]) (= (3, 5)) se encuentra entre |3 – 5| (= 2) y |3 + 5| (= 8).
El par (arr[2], arr[3]) (= (5, 7)) se encuentra entre |5 – 7| (= 2) y |5 + 7| (= 12).Entrada: arr[] = {-4, 1, 9, 7, -1, 2, 8}
Salida: 9
Planteamiento: El problema planteado se puede resolver analizando los siguientes casos:
- Si X es positivo y Y es positivo:
- |X-Y| queda |X – Y|.
- |X+Y| queda |X + Y|.
- Si X es negativo y Y es positivo:
- |X-Y| se convierte en |-(X + Y)|, es decir , |X + Y|.
- |X+Y| se convierte en |-(X – Y)|, es decir , |X – Y|.
- Si X es positivo y Y es negativo:
- |X-Y| se convierte en |X + Y|.
- |X+Y| se convierte en |X – Y|.
- Si X es negativo y Y es negativo:
- |X-Y| queda |X – Y|.
- |X+Y| queda |X + Y|.
Está claro de los casos anteriores, que |X – Y| y |X + Y| son a lo sumo valores de intercambio, lo que no cambia la solución.
Por lo tanto, si un par es válido para (X, Y), entonces también será válido para cualquiera de los casos anteriores como (-X, Y) . Por lo tanto, la tarea se reduce a simplemente tomar valores absolutos de X e Y mientras se encuentra la solución, es decir, encontrar (X, Y), donde |X – Y| ≤ X, Y ≤ X + Y .
Siga los pasos a continuación para resolver el problema:
- Tome valores absolutos de todos los elementos presentes en la array arr[].
- Ordene la array arr[] .
- Inicializa una variable, digamos left , como 0.
- Inicialice una variable, digamos ans, para almacenar el recuento de pares válidos.
- Recorra la array arr[] usando una variable, digamos right , y realice los siguientes pasos:
- Incremente a la izquierda hasta que 2 *arr[left] sea menor que arr[right] .
- Agregue el valor (i – izquierda) a ans para incluir el número de pares válidos.
- Después de completar los pasos anteriores, imprima el valor de ans 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 pairs (i, j) such that
// |arr[i]| and |arr[j]| lies in between
// |arr[i] - arr[j]| and |arr[i] + arr[j]|
void findPairs(int arr[], int N)
{
// Calculate absolute value
// of all array elements
for (int i = 0; i < N; i++)
arr[i] = abs(arr[i]);
// Sort the array
sort(arr, arr + N);
int left = 0;
// Stores the count of pairs
int ans = 0;
// Traverse the array
for (int right = 0; right < N; right++) {
while (2 * arr[left] < arr[right])
// Increment left
left++;
// Add to the current
// count of pairs
ans += (right - left);
}
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
findPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG{
// Function to find pairs (i, j) such that
// |arr[i]| and |arr[j]| lies in between
// |arr[i] - arr[j]| and |arr[i] + arr[j]|
static void findPairs(int arr[], int N)
{
// Calculate absolute value
// of all array elements
for(int i = 0; i < N; i++)
arr[i] = Math.abs(arr[i]);
// Sort the array
Arrays.sort(arr);
int left = 0;
// Stores the count of pairs
int ans = 0;
// Traverse the array
for(int right = 0; right < N; right++)
{
while (2 * arr[left] < arr[right])
// Increment left
left++;
// Add to the current
// count of pairs
ans += (right - left);
}
// Print the answer
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 7 };
int N = arr.length;
findPairs(arr, N);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to find pairs (i, j) such that # |arr[i]| and |arr[j]| lies in between # |arr[i] - arr[j]| and |arr[i] + arr[j]| def findPairs(arr, N): # Calculate absolute value # of all array elements for i in range(N): arr[i] = abs(arr[i]) # Sort the array arr.sort() left = 0 # Stores the count of pairs ans = 0 # Traverse the array for right in range(N): while (2 * arr[left] < arr[right]): # Increment left left += 1 # Add to the current # count of pairs ans += (right - left) # Print the answer print(ans) # Driver Code if __name__ == "__main__": arr = [1, 3, 5, 7] N = len(arr) findPairs(arr, N) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find pairs (i, j) such that
// |arr[i]| and |arr[j]| lies in between
// |arr[i] - arr[j]| and |arr[i] + arr[j]|
static void findPairs(int []arr, int N)
{
// Calculate absolute value
// of all array elements
for(int i = 0; i < N; i++)
arr[i] = Math.Abs(arr[i]);
// Sort the array
Array.Sort(arr);
int left = 0;
// Stores the count of pairs
int ans = 0;
// Traverse the array
for(int right = 0; right < N; right++)
{
while (2 * arr[left] < arr[right])
// Increment left
left++;
// Add to the current
// count of pairs
ans += (right - left);
}
// Print the answer
Console.Write(ans);
}
// Driver Code
public static void Main(string[] args)
{
int []arr = { 1, 3, 5, 7 };
int N = arr.Length;
findPairs(arr, N);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program for the above approach
// Function to find pairs (i, j) such that
// |arr[i]| and |arr[j]| lies in between
// |arr[i] - arr[j]| and |arr[i] + arr[j]|
function findPairs(arr, N)
{
// Calculate absolute value
// of all array elements
for (let i = 0; i < N; i++)
arr[i] = Math.abs(arr[i]);
// Sort the array
arr.sort((a, b) => a - b);
let left = 0;
// Stores the count of pairs
let ans = 0;
// Traverse the array
for (let right = 0; right < N; right++) {
while (2 * arr[left] < arr[right])
// Increment left
left++;
// Add to the current
// count of pairs
ans += (right - left);
}
// Print the answer
document.write(ans);
}
// Driver Code
let arr = [ 1, 3, 5, 7 ];
let N = arr.length;
findPairs(arr, N);
// This code is contributed by Manoj.
</script>
Producción:
2
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)