Dada una array arr[] que consta de N enteros distintos y un entero K , la tarea es encontrar el tamaño máximo posible de un subconjunto de modo que ningún elemento del subconjunto sea K veces cualquier otro elemento del subconjunto (es decir, no hay tal par { n, m} debe estar presente en el subconjunto tal que m = n * K o n = m * K ).
Ejemplos:
Entrada: arr[] = {2, 8, 6, 5, 3}, K = 2
Salida: 4
Explicación:
El único par posible existente en la array con un elemento siendo K( = 2) veces el otro es {6, 3 }.
Por lo tanto, se pueden considerar todos los subconjuntos posibles que no contengan ambos elementos del par {6, 3} juntos.
Por lo tanto, el subconjunto más largo posible puede tener una longitud de 4.Entrada: arr[] = {1, 4, 3, 2}, K = 3
salida: 3
Enfoque:
siga los pasos a continuación para resolver el problema:
- Encuentre la cantidad de pares posibles de modo que un elemento sea K veces el otro de la array dada
- Ordene la array en orden creciente de elementos.
- Recorra la array y almacene los índices de frecuencia de los elementos de la array en Map .
- Inicialice una array visitada para marcar cada índice, ya sea que ese elemento esté incluido ( 0 ) o no ( 1 ) en el subconjunto.
- Recorra la array nuevamente y para cada índice que tenga vis[i] = 0 , verifique si arr[i] * K está presente en el Mapa o no. Si lo encuentra, aumente el recuento de pares y establezca vis[mp[arr[i] * K]] = 1 .
- Finalmente, imprima N – recuento de pares como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function to find the maximum
// size of the required subset
int findMaxLen(vector<ll>& a, ll k)
{
// Size of the array
int n = a.size();
// Sort the array
sort(a.begin(), a.end());
// Stores which index is
// included or excluded
vector<bool> vis(n, 0);
// Stores the indices of
// array elements
map<int, int> mp;
for (int i = 0; i < n; i++) {
mp[a[i]] = i;
}
// Count of pairs
int c = 0;
// Iterate through all
// the element
for (int i = 0; i < n; ++i) {
// If element is included
if (vis[i] == false) {
int check = a[i] * k;
// Check if a[i] * k is present
// in the array or not
if (mp.find(check) != mp.end()) {
// Increase count of pair
c++;
// Exclude the pair
vis[mp[check]] = true;
}
}
}
return n - c;
}
// Driver code
int main()
{
int K = 3;
vector<ll> arr = { 1, 4, 3, 2 };
cout << findMaxLen(arr, K);
}
Java
// Java implementation of
// the above approach
import java.util.*;
class GFG{
// Function to find the maximum
// size of the required subset
static int findMaxLen(int[] a, int k)
{
// Size of the array
int n = a.length;
// Sort the array
Arrays.sort(a);
// Stores which index is
// included or excluded
boolean []vis = new boolean[n];
// Stores the indices of
// array elements
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
for(int i = 0; i < n; i++)
{
mp.put(a[i], i);
}
// Count of pairs
int c = 0;
// Iterate through all
// the element
for(int i = 0; i < n; ++i)
{
// If element is included
if (vis[i] == false)
{
int check = a[i] * k;
// Check if a[i] * k is present
// in the array or not
if (mp.containsKey(check))
{
// Increase count of pair
c++;
// Exclude the pair
vis[mp.get(check)] = true;
}
}
}
return n - c;
}
// Driver code
public static void main(String[] args)
{
int K = 3;
int []arr = { 1, 4, 3, 2 };
System.out.print(findMaxLen(arr, K));
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 implementation of
# the above approach
# Function to find the maximum
# size of the required subset
def findMaxLen(a, k):
# Size of the array
n = len(a)
# Sort the array
a.sort()
# Stores which index is
# included or excluded
vis = [0] * n
# Stores the indices of
# array elements
mp = {}
for i in range(n):
mp[a[i]] = i
# Count of pairs
c = 0
# Iterate through all
# the element
for i in range(n):
# If element is included
if(vis[i] == False):
check = a[i] * k
# Check if a[i] * k is present
# in the array or not
if(check in mp.keys()):
# Increase count of pair
c += 1
# Exclude the pair
vis[mp[check]] = True
return n - c
# Driver Code
if __name__ == '__main__':
K = 3
arr = [ 1, 4, 3, 2 ]
print(findMaxLen(arr, K))
# This code is contributed by Shivam Singh
C#
// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum
// size of the required subset
static int findMaxLen(int[] a, int k)
{
// Size of the array
int n = a.Length;
// Sort the array
Array.Sort(a);
// Stores which index is
// included or excluded
bool []vis = new bool[n];
// Stores the indices of
// array elements
Dictionary<int,
int> mp = new Dictionary<int,
int>();
for(int i = 0; i < n; i++)
{
mp.Add(a[i], i);
}
// Count of pairs
int c = 0;
// Iterate through all
// the element
for(int i = 0; i < n; ++i)
{
// If element is included
if (vis[i] == false)
{
int check = a[i] * k;
// Check if a[i] * k is present
// in the array or not
if (mp.ContainsKey(check))
{
// Increase count of pair
c++;
// Exclude the pair
vis[mp[check]] = true;
}
}
}
return n - c;
}
// Driver code
public static void Main(String[] args)
{
int K = 3;
int []arr = { 1, 4, 3, 2 };
Console.Write(findMaxLen(arr, K));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript implementation of
// the above approach
// Function to find the maximum
// size of the required subset
function findMaxLen(a, k)
{
// Size of the array
let n = a.length;
// Sort the array
a.sort();
// Stores which index is
// included or excluded
let vis = Array.from({length: n}, (_, i) => 0);
// Stores the indices of
// array elements
let mp = new Map();
for(let i = 0; i < n; i++)
{
mp.set(a[i], i);
}
// Count of pairs
let c = 0;
// Iterate through all
// the element
for(let i = 0; i < n; ++i)
{
// If element is included
if (vis[i] == false)
{
let check = a[i] * k;
// Check if a[i] * k is present
// in the array or not
if (mp.has(check))
{
// Increase count of pair
c++;
// Exclude the pair
vis[mp.get(check)] = true;
}
}
}
return n - c;
}
// Driver code
let K = 3;
let arr = [ 1, 4, 3, 2 ];
document.write(findMaxLen(arr, K));
// This code is contributed by souravghosh0416.
</script>
Producción:
3
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)