Cuente el número de pares (i, j) tales que arr[i] sea divisible por arr[j] o arr[j] sea divisible por arr[i]

Dada una array arr[] de N enteros, la tarea es encontrar el recuento de pares de índices no ordenados (i, j) tales que i != j y 0 <=i < j < N y arr[i] es divisible por arr[j] o arr[j] es divisible por arr[i] .
Ejemplos: 
 

Entrada: arr[] = {2, 4} 
Salida: 1 
(0, 1) es el único par de índices posible.
Entrada: arr[] = {3, 2, 4, 2, 6} 
Salida: 6 
Los pares posibles son (0, 4), (1, 2), (1, 3), (1, 4), (2, 3) y (3, 4). 
 

Enfoque: la idea es encontrar el elemento máximo de la array y usar las variables count para almacenar el número de pares no ordenados, array freq[] para almacenar la frecuencia de los elementos de la array. Ahora recorra la array y para cada elemento encuentre los números que son divisibles por el i-ésimo número de la array y que son menores o iguales que el número máximo de la array. Si el número existe en la array, actualice la variable count .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find number of unordered pairs
int freqPairs(int arr[], int n)
{
 
    // Maximum element from the array
    int max = *(std::max_element(arr, arr + n));
 
    // Array to store the frequency of each
    // element
    int freq[max + 1] = { 0 };
 
    // Stores the number of unordered pairs
    int count = 0;
 
    // Store the frequency of each element
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;
 
    // Find the number of unordered pairs
    for (int i = 0; i < n; i++) {
        for (int j = 2 * arr[i]; j <= max; j += arr[i]) {
 
            // If the number j divisible by ith element
            // is present in the array
            if (freq[j] >= 1)
                count += freq[j];
        }
 
        // If the ith element of the array
        // has frequency more than one
        if (freq[arr[i]] > 1) {
            count += freq[arr[i]] - 1;
            freq[arr[i]]--;
        }
    }
 
    return count;
}
 
// Driver code
int main()
{
 
    int arr[] = { 3, 2, 4, 2, 6 };
    int n = (sizeof(arr) / sizeof(arr[0]));
 
    cout << freqPairs(arr, n);
 
    return 0;
}

import java.util.Arrays;
 
// Java implementation of the approach
class GFG
{
 
    // Function to find number of unordered pairs
    static int freqPairs(int arr[], int n)
    {
 
        // Maximum element from the array
        int max = Arrays.stream(arr).max().getAsInt();
 
        // Array to store the frequency of each
        // element
        int freq[] = new int[max + 1];
 
        // Stores the number of unordered pairs
        int count = 0;
 
        // Store the frequency of each element
        for (int i = 0; i < n; i++)
        {
            freq[arr[i]]++;
        }
 
        // Find the number of unordered pairs
        for (int i = 0; i < n; i++)
        {
            for (int j = 2 * arr[i]; j <= max; j += arr[i])
            {
 
                // If the number j divisible by ith element
                // is present in the array
                if (freq[j] >= 1)
                {
                    count += freq[j];
                }
            }
 
            // If the ith element of the array
            // has frequency more than one
            if (freq[arr[i]] > 1)
            {
                count += freq[arr[i]] - 1;
                freq[arr[i]]--;
            }
        }
 
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = {3, 2, 4, 2, 6};
        int n = arr.length;
 
        System.out.println(freqPairs(arr, n));
    }
}
 
// This code has been contributed by 29AjayKumar

# Python 3 implementation of the approach
 
# Function to find number of unordered pairs
def freqPairs(arr, n):
     
    # Maximum element from the array
    max = arr[0]
    for i in range(len(arr)):
        if arr[i] > max:
            max = arr[i]
 
    # Array to store the frequency of
    # each element
    freq = [0 for i in range(max + 1)]
 
    # Stores the number of unordered pairs
    count = 0
 
    # Store the frequency of each element
    for i in range(n):
        freq[arr[i]] += 1
 
    # Find the number of unordered pairs
    for i in range(n):
        for j in range(2 * arr[i],
                           max + 1, arr[i]):
             
            # If the number j divisible by ith
            # element is present in the array
            if (freq[j] >= 1):
                count += freq[j]
 
        # If the ith element of the array
        # has frequency more than one
        if (freq[arr[i]] > 1):
            count += freq[arr[i]] - 1
            freq[arr[i]] -= 1
 
    return count
 
# Driver code
if __name__ == '__main__':
    arr = [3, 2, 4, 2, 6]
    n = len(arr)
 
    print(freqPairs(arr, n))
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation of the approach
using System;
using System.Linq;
 
class GFG
{
 
    // Function to find number of unordered pairs
    static int freqPairs(int []arr, int n)
    {
 
        // Maximum element from the array
        int max = arr.Max();
 
        // Array to store the frequency of each
        // element
        int []freq = new int[max + 1];
 
        // Stores the number of unordered pairs
        int count = 0;
 
        // Store the frequency of each element
        for (int i = 0; i < n; i++)
        {
            freq[arr[i]]++;
        }
 
        // Find the number of unordered pairs
        for (int i = 0; i < n; i++)
        {
            for (int j = 2 * arr[i]; j <= max; j += arr[i])
            {
 
                // If the number j divisible by ith element
                // is present in the array
                if (freq[j] >= 1)
                {
                    count += freq[j];
                }
            }
 
            // If the ith element of the array
            // has frequency more than one
            if (freq[arr[i]] > 1)
            {
                count += freq[arr[i]] - 1;
                freq[arr[i]]--;
            }
        }
 
        return count;
    }
 
    // Driver code
    public static void Main(String []args)
    {
        int []arr = {3, 2, 4, 2, 6};
        int n = arr.Length;
 
        Console.WriteLine(freqPairs(arr, n));
    }
}
 
// This code has been contributed by Arnab Kundu

<?php
// PHP implementation of the approach
 
// Function to find number of unordered pairs
function freqPairs($arr, $n)
{
 
    // Maximum element from the array
    $max = max($arr);
 
    // Array to store the frequency of
    // each element
    $freq = array_fill(0, $max + 1, 0);
 
    // Stores the number of unordered pairs
    $count = 0;
 
    // Store the frequency of each element
    for ($i = 0; $i < $n; $i++)
        $freq[$arr[$i]]++;
 
    // Find the number of unordered pairs
    for ($i = 0; $i < $n; $i++)
    {
        for ($j = 2 * $arr[$i];
             $j <= $max; $j += $arr[$i])
        {
 
            // If the number j divisible by ith
            // element is present in the array
            if ($freq[$j] >= 1)
                $count += $freq[$j];
        }
 
        // If the ith element of the array
        // has frequency more than one
        if ($freq[$arr[$i]] > 1)
        {
            $count += $freq[$arr[$i]] - 1;
            $freq[$arr[$i]]--;
        }
    }
 
    return $count;
}
 
// Driver code
$arr = array(3, 2, 4, 2, 6);
$n = count($arr);
 
echo freqPairs($arr, $n);
 
// This code is contributed by Ryuga
?>

<script>
// Javascript implementation of the approach
 
// Function to find number of unordered pairs
function freqPairs(arr, n)
{
 
    // Maximum element from the array
    let max = Math.max(...arr);
 
    // Array to store the frequency of each
    // element
    let freq = new Array(max + 1).fill(0);
 
    // Stores the number of unordered pairs
    let count = 0;
 
    // Store the frequency of each element
    for (let i = 0; i < n; i++)
        freq[arr[i]]++;
 
    // Find the number of unordered pairs
    for (let i = 0; i < n; i++) {
        for (let j = 2 * arr[i]; j <= max; j += arr[i]) {
 
            // If the number j divisible by ith element
            // is present in the array
            if (freq[j] >= 1)
                count += freq[j];
        }
 
        // If the ith element of the array
        // has frequency more than one
        if (freq[arr[i]] > 1) {
            count += freq[arr[i]] - 1;
            freq[arr[i]]--;
        }
    }
 
    return count;
}
 
// Driver code
 
    let arr = [ 3, 2, 4, 2, 6 ];
    let n = arr.length;
 
    document.write(freqPairs(arr, n));
 
</script>

6

Complejidad de tiempo: O(max*N), donde max es el valor máximo de la array.

Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.