Recuento de pares distintos que tienen un elemento como K veces el otro

Dada una array arr[] y un entero K, encuentre el número máximo de pares que se pueden formar de modo que un elemento sea K veces el otro, es decir, arr[i]=K*arr[j] .

Ejemplos:

Entrada: arr[] = {1, 2, 1, 2, 4} K = 2
Salida: 2
Explicación: Hay dos formas posibles de construir pares: ({1, 2}, {1, 2}) y ({ 1, 2}, {2, 4}).

Entrada: a = {5, 4, 3, 2, 1} K = 2
Salida: 1
Explicación: Podemos construir el conjunto {1, 2} o el conjunto {2, 4}.

Enfoque: ordene la array dada arr[] y verifique todos los pares posibles de la array arr[] y verifique si una determinada (i, j) arr[i]=2*arr[j]. Siga los pasos a continuación para resolver el problema:

• Ordene la array arr[] usando la función de ordenación en C++ STL .
• Inicialice un vector utilizado para mantener el recuento de elementos ya utilizados.
• Inicialice la variable ans como 0 para almacenar el recuento de todos los pares posibles.
• Iterar sobre el rango [0, N-1] usando la variable i   y realizar los siguientes pasos: 
  • Itere sobre el rango [l, N-1] usando la variable j y haga lo siguiente:
    • Si el valor de used[j] y used[i] es falso y arr[j]=K*arr[i] , entonces, establezca el valor de used[i] y used[j] en verdadero y aumente el valor de responda por 1 y rompa el ciclo .
• Finalmente, después de completar los pasos anteriores, imprima el valor de ans.

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

// C++ program for the above approach.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum number
// of pairs.
int maxPairs(vector<int> a, int k)
{
    // Sort the array.
    sort(a.begin(), a.end());
    int n = a.size(), ans = 0;
 
    // mark as used
    vector<bool> used(n);
 
    // iterate over all elements
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // if condition is satisfied,
            // pair the elements
            if (!used[j]
                && a[j] == k * a[i]
                && !used[i]) {
                used[j] = used[i] = true;
                ans++;
                break;
            }
        }
    }
 
    return ans;
}
 
// Driver Code
int32_t main()
{
    vector<int> a{ 1, 2, 1, 2, 4 };
    int k = 2;
    cout << maxPairs(a, k);
    return 0;
}

// Java program for the above approach.
 
 
import java.util.Arrays;
 
class GFG {
 
    // Function to find the maximum number
    // of pairs.
public static int maxPairs(int[] a, int k)
{
    // Sort the array.
    Arrays.sort(a);
    int n = a.length, ans = 0;
 
    // mark as used
    boolean[] used = new boolean[n];
 
 
    // iterate over all elements
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // if condition is satisfied,
            // pair the elements
            if (!used[j]
                && a[j] == k * a[i]
                && !used[i]) {
                used[i] =  true;
                used[j] = used[i];
                ans++;
                break;
            }
        }
    }
 
    return ans;
}
 
    // Driver Code
    public static void main(String args[])
    {
        int[] a = {1, 2, 1, 2, 4};
        int k = 2;
        System.out.println(maxPairs(a, k));
    }
}
 
// This code is contributed by _saurabh_jaiswal.

# Python Program for the above approach
 
# Function to find the maximum number
# of pairs.
def maxPairs(a, k):
 
    # Sort the array.
    a.sort()
    n = len(a)
    ans = 0
 
    # mark as used
    used = [False] * n
 
    # iterate over all elements
    for i in range(0, n):
        for j in range(i + 1, n):
 
            # if condition is satisfied,
            # pair the elements
            if (used[j] == False and a[j] == k * a[i] and used[i] == False):
                used[j] = used[j] = True
                ans += 1
                break
 
    return ans
 
# Driver Code
a = [1, 2, 1, 2, 4]
k = 2
print(maxPairs(a, k))
 
# This code is contributed by _saurabh_jaiswal

// C# program for the above approach.
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the maximum number
// of pairs.
static int maxPairs(List<int> a, int k)
{
   
    // Sort the array.
    a.Sort();
    int n = a.Count, ans = 0;
 
    // mark as used
    int [] Ar = new int[n];
    List<int> used = new List<int>(Ar);
 
    // iterate over all elements
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // if condition is satisfied,
            // pair the elements
            if (used[j]==0
                && a[j] == k * a[i]
                && used[i]==0) {
                used[j] = used[i] = 1;
                ans++;
                break;
            }
        }
    }
 
    return ans;
}
 
// Driver Code
  public static void Main(){
    List<int> a = new List<int>(){ 1, 2, 1, 2, 4 };
    int k = 2;
    Console.Write(maxPairs(a, k));
  }
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
        // JavaScript Program for the above approach
 
        // Function to find the maximum number
        // of pairs.
        function maxPairs(a, k)
        {
         
            // Sort the array.
            a.sort(function (x, y) { return x - y });
            let n = a.length, ans = 0;
 
            // mark as used
            let used = new Array(n).fill(false);
 
            // iterate over all elements
            for (let i = 0; i < n; i++) {
                for (let j = i + 1; j < n; j++) {
 
                    // if condition is satisfied,
                    // pair the elements
                    if (used[j] == false && a[j] == k * a[i] && used[i] == false) {
                        used[j] = used[j] = true;
                        ans++;
                        break;
                    }
                }
            }
 
            return ans;
        }
 
        // Driver Code
        let a = [1, 2, 1, 2, 4];
        let k = 2;
        document.write(maxPairs(a, k));
         
    // This code is contributed by Potta Lokesh
    </script>

2

Complejidad de tiempo: O(N^2)
Complejidad de espacio: O(N)