Cuente los elementos en la primera array con una diferencia absoluta mayor que K con un elemento en la segunda array

Dadas dos arrays arr1[] y arr2[] y un entero K , nuestra tarea es encontrar los elementos numéricos en la primera array, para un elemento x, en arr1[] , existe al menos un elemento y, en arr2[] tal que la diferencia absoluta de x e y es mayor que el entero K .

Ejemplos: 

Entrada: arr1 = {3, 1, 4}, arr2 = {5, 1, 2}, K = 2 
Salida: 2 
Explicación: 
Tales elementos son 1 y 4. 
Para 1, arr2[] tiene 5 y abs(1 – 5) = 4, que es mayor que 2. 
Para 4, arr2[] tiene 1 y abs(4 – 1) = 3, que nuevamente es mayor que 2.

Entrada: arr1 = {1, 2}, arr2 = {4, 6}, K = 3 
Salida: 2 
Explicación: 
Dichos elementos son 1 y 2. 
Para 1, arr2[] tiene 6 y abs(1 – 6) = 5 que es mayor que 3. 
Para 2, arr2[] tiene 6 y abs(2 – 6) = 4 que es mayor que 3. 
 

Enfoque ingenuo: iterar para cada elemento en arr1[] y verificar si existe o no un elemento en arr2 tal que su diferencia absoluta sea mayor que el valor K. 

Complejidad temporal: O(N * M) donde N y M son los tamaños de los arreglos 1 y 2 respectivamente.

Enfoque eficiente: para optimizar el método anterior, debemos observar que para cada elemento en arr1[], solo necesitamos el elemento más pequeño y el más grande de arr2[] para verificar si es distante o no. Para cada elemento x, en arr1, si la diferencia absoluta del valor más pequeño o más grande y x es mayor que K, entonces ese elemento es distante.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to count elements in first Array
// with absolute difference greater than K
// with an element in second Array
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the such elements
void countDist(int arr1[], int n, int arr2[],
               int m, int k)
{
    // Store count of required elements in arr1
    int count = 0;
 
    // Initialise the smallest and the largest
    // value from the second array arr2[]
    int smallest = arr2[0];
    int largest = arr2[0];
 
    // Find the smallest and
    // the largest element in arr2
    for (int i = 0; i < m; i++) {
        smallest = max(smallest, arr2[i]);
        largest = min(largest, arr1[i]);
    }
    for (int i = 0; i < n; i++) {
 
        // Check if absolute difference of smallest
        // and arr1[i] or largest and arr1[i] is > K
        // then arr[i] is a required element
        if (abs(arr1[i] - smallest) > k
            || abs(arr1[i] - largest) > k)
            count++;
    }
 
    // Print the final result
    cout << count;
}
 
// Driver code
int main()
{
    int arr1[] = { 3, 1, 4 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int arr2[] = { 5, 1, 2 };
    int m = sizeof(arr2) / sizeof(arr2[0]);
    int k = 2;
 
    countDist(arr1, n, arr2, m, k);
 
    return 0;
}

// Java program to count elements in first Array
// with absolute difference greater than K
// with an element in second Array
class GFG{
 
// Function to count the such elements
static void countDist(int arr1[], int n,
                      int arr2[], int m,
                      int k)
{
    // Store count of required elements in arr1
    int count = 0;
 
    // Initialise the smallest and the largest
    // value from the second array arr2[]
    int smallest = arr2[0];
    int largest = arr2[0];
 
    // Find the smallest and
    // the largest element in arr2
    for(int i = 0; i < m; i++)
    {
       smallest = Math.max(smallest, arr2[i]);
       largest = Math.min(largest, arr1[i]);
    }
    for(int i = 0; i < n; i++)
    {
 
       // Check if absolute difference
       // of smallest and arr1[i] or
       // largest and arr1[i] is > K
       // then arr[i] is a required element
       if (Math.abs(arr1[i] - smallest) > k ||
           Math.abs(arr1[i] - largest) > k)
           count++;
    }
 
    // Print the final result
    System.out.print(count);
}
 
// Driver code
public static void main(String[] args)
{
    int arr1[] = { 3, 1, 4 };
    int n = arr1.length;
    int arr2[] = { 5, 1, 2 };
    int m = arr2.length;
    int k = 2;
 
    countDist(arr1, n, arr2, m, k);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to count elements in the first Array
# with an absolute difference greater than K
# with an element in the second Array
 
# Function to count the such elements
def countDist(arr1, n, arr2, m, k):
     
    # Store count of required elements in arr1
    count = 0
 
    # Initialise the smallest and the largest
    # value from the second array arr2[]
    smallest = arr2[0]
    largest = arr2[0]
 
    # Find the smallest and
    # the largest element in arr2
    for i in range(m):
        smallest = max(smallest, arr2[i])
        largest = min(largest, arr1[i])
 
    for i in range(n):
 
        # Check if absolute difference of smallest
        # and arr1[i] or largest and arr1[i] is > K
        # then arr[i] is a required element
        if (abs(arr1[i] - smallest) > k
            or abs(arr1[i] - largest) > k):
            count += 1
 
    # Print final result
    print(count)
 
 
# Driver code
if __name__ == '__main__':
     
    arr1= [ 3, 1, 4 ]
    n = len(arr1)
    arr2= [ 5, 1, 2 ]
    m = len(arr2)
    k = 2
 
    countDist(arr1, n, arr2, m, k)
     
# This code is contributed by mohit kumar 29

// C# program to count elements in first array
// with absolute difference greater than K
// with an element in second Array
using System;
 
class GFG{
 
// Function to count the such elements
static void countDist(int []arr1, int n,
                      int []arr2, int m,
                      int k)
{
    // Store count of required elements in arr1
    int count = 0;
 
    // Initialise the smallest and the largest
    // value from the second array arr2[]
    int smallest = arr2[0];
    int largest = arr2[0];
 
    // Find the smallest and
    // the largest element in arr2
    for(int i = 0; i < m; i++)
    {
       smallest = Math.Max(smallest, arr2[i]);
       largest = Math.Min(largest, arr1[i]);
    }
    for(int i = 0; i < n; i++)
    {
        
       // Check if absolute difference
       // of smallest and arr1[i] or
       // largest and arr1[i] is > K
       // then arr[i] is a required element
       if (Math.Abs(arr1[i] - smallest) > k ||
           Math.Abs(arr1[i] - largest) > k)
           count++;
    }
 
    // Print the readonly result
    Console.Write(count);
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr1 = { 3, 1, 4 };
    int n = arr1.Length;
    int []arr2 = { 5, 1, 2 };
    int m = arr2.Length;
    int k = 2;
 
    countDist(arr1, n, arr2, m, k);
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program to count elements in
// first Array with absolute difference
// greater than K with an element in
// second Array   
 
// Function to count the such elements
function countDist(arr1, n, arr2, m, k)
{
     
    // Store count of required elements in arr1
    var count = 0;
 
    // Initialise the smallest and the largest
    // value from the second array arr2
    var smallest = arr2[0];
    var largest = arr2[0];
 
    // Find the smallest and
    // the largest element in arr2
    for(i = 0; i < m; i++)
    {
        smallest = Math.max(smallest, arr2[i]);
        largest = Math.min(largest, arr1[i]);
    }
    for(i = 0; i < n; i++)
    {
         
        // Check if absolute difference
        // of smallest and arr1[i] or
        // largest and arr1[i] is > K
        // then arr[i] is a required element
        if (Math.abs(arr1[i] - smallest) > k ||
            Math.abs(arr1[i] - largest) > k)
            count++;
    }
 
    // Print the final result
    document.write(count);
}
 
// Driver code
var arr1 = [ 3, 1, 4 ];
var n = arr1.length;
var arr2 = [ 5, 1, 2 ];
var m = arr2.length;
var k = 2;
 
countDist(arr1, n, arr2, m, k);
 
// This code is contributed by umadevi9616
 
</script>

2

Complejidad de tiempo: O(N + M), donde N y M son los tamaños de las arrays dadas.
Espacio Auxiliar: O(1).