Dada una array arr[] y un entero positivo K , la tarea es encontrar el recuento máximo de pares disjuntos (arr[i], arr[j]) tal que arr[j] ≥ K * arr[i] .
Ejemplos:
Entrada: arr[] = { 1, 9, 4, 7, 3 }, K = 2
Salida: 2
Explicación:
Puede haber 2 pares posibles que se pueden formar a partir de la array dada, es decir, (4, 1) y (7, 3) que satisfagan las condiciones dadas.Entrada: arr[] = {2, 3, 4, 5, 6, 7, 8, 9}, K = 3
Salida: 2
Enfoque: El problema dado se puede resolver utilizando el enfoque de dos punteros . Siga los pasos a continuación para resolver el problema dado:
- Ordena la array dada en orden creciente .
- Inicialice dos variables i y j como 0 y (N / 2) respectivamente y conteo variable que almacene el conteo máximo resultante de pares.
- Recorra la array dada sobre el rango [0, N/2] y realice los siguientes pasos:
- Incremente el valor de j hasta que j < N y arr[j] < K * arr[i] .
- Si el valor de j es menor que N , incremente el conteo de pares en 1 .
- Incremente el valor de j en 1 .
- Después de completar los pasos anteriores, imprima el valor de conteo 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 the maximum count
// of disjoint pairs such that arr[i]
// is at least K*arr[j]
int maximizePairs(int arr[], int n, int k)
{
// Sort the array
sort(arr, arr + n);
// Initialize the two pointers
int i = 0, j = n / 2;
// Stores the total count of pairs
int count = 0;
for (i = 0; i < n / 2; i++) {
// Increment j until a valid
// pair is found or end of the
// array is reached
while (j < n
&& (k * arr[i]) > arr[j])
j++;
// If j is not the end of the
// array, then a valid pair
if (j < n)
count++;
j++;
}
// Return the possible count
return count;
}
// Driver Code
int main()
{
int arr[] = { 1, 9, 4, 7, 3 };
int N = sizeof(arr) / sizeof(int);
int K = 2;
cout << maximizePairs(arr, N, K);
return 0;
}
Java
// Java code for above approach
import java.util.*;
class GFG{
// Function to find the maximum count
// of disjoint pairs such that arr[i]
// is at least K*arr[j]
static int maximizePairs(int arr[], int n, int k)
{
// Sort the array
Arrays.sort(arr);
// Initialize the two pointers
int i = 0, j = n / 2;
// Stores the total count of pairs
int count = 0;
for (i = 0; i < n / 2; i++) {
// Increment j until a valid
// pair is found or end of the
// array is reached
while (j < n
&& (k * arr[i]) > arr[j])
j++;
// If j is not the end of the
// array, then a valid pair
if (j < n)
count++;
j++;
}
// Return the possible count
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 9, 4, 7, 3 };
int N = arr.length;
int K = 2;
System.out.print(maximizePairs(arr, N, K));
}
}
// This code is contributed by avijitmondal1998.
Python3
# Python 3 program for the above approach # Function to find the maximum count # of disjoint pairs such that arr[i] # is at least K*arr[j] def maximizePairs(arr, n, k): # Sort the array arr.sort() # Initialize the two pointers i = 0 j = n // 2 # Stores the total count of pairs count = 0 for i in range(n//2): # Increment j until a valid # pair is found or end of the # array is reached while (j < n and (k * arr[i]) > arr[j]): j += 1 # If j is not the end of the # array, then a valid pair if (j < n): count += 1 j += 1 # Return the possible count return count # Driver Code if __name__ == '__main__': arr = [1, 9, 4, 7, 3] N = len(arr) K = 2 print(maximizePairs(arr, N, K)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# code for above approach
using System;
class GFG{
// Function to find the maximum count
// of disjoint pairs such that arr[i]
// is at least K*arr[j]
static int maximizePairs(int []arr, int n, int k)
{
// Sort the array
Array.Sort(arr);
// Initialize the two pointers
int i = 0, j = n / 2;
// Stores the total count of pairs
int count = 0;
for (i = 0; i < n / 2; i++) {
// Increment j until a valid
// pair is found or end of the
// array is reached
while (j < n
&& (k * arr[i]) > arr[j])
j++;
// If j is not the end of the
// array, then a valid pair
if (j < n)
count++;
j++;
}
// Return the possible count
return count;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 9, 4, 7, 3 };
int N = arr.Length;
int K = 2;
Console.Write(maximizePairs(arr, N, K));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum count
// of disjoint pairs such that arr[i]
// is at least K*arr[j]
function maximizePairs(arr, n, k) {
// Sort the array
arr.sort((a, b) => a - b);
// Initialize the two pointers
let i = 0,
j = Math.floor(n / 2);
// Stores the total count of pairs
let count = 0;
for (i = 0; i < Math.floor(n / 2); i++) {
// Increment j until a valid
// pair is found or end of the
// array is reached
while (j < n && k * arr[i] > arr[j]) j++;
// If j is not the end of the
// array, then a valid pair
if (j < n) count++;
j++;
}
// Return the possible count
return count;
}
// Driver Code
let arr = [1, 9, 4, 7, 3];
let N = arr.length;
let K = 2;
document.write(maximizePairs(arr, N, K));
// This code is contributed by gfgking.
</script>
Producción:
2
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dwivediyash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA