El subconjunto más grande posible para una array que satisface la condición dada

Dada una array arr[] y un entero K . La tarea es encontrar el tamaño del subconjunto máximo tal que cada par del subconjunto (X, Y) sea de la forma Y != (X * K) donde X < Y .

Ejemplos: 

Entrada: arr[] = {2, 3, 6, 5, 4, 10}, K = 2 
Salida: 3 
{2, 3, 5} es el subconjunto requerido

Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, K = 2 
Salida: 6 

Acercarse:  

• Ordenar todos los elementos de la array.
• Cree un conjunto vacío de enteros S , que contendrá los elementos del subconjunto.
• Recorra la array ordenada, y para cada entero x en la array: 
  • Si x % k = 0 o x / k no está ya presente en S entonces inserte x en S .
  • De lo contrario, descarte x y verifique el siguiente elemento.
• Imprime el tamaño del conjunto S al final.

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 return the size of the required sub-set
int sizeSubSet(int a[], int k, int n)
{
    // Sort the array
    sort(a, a + n);
 
    // Set to store the contents of the required sub-set
    unordered_set<int> s;
 
    // Insert the elements satisfying the conditions
    for (int i = 0; i < n; i++) {
        if (a[i] % k != 0 || s.count(a[i] / k) == 0)
            s.insert(a[i]);
    }
 
    // Return the size of the set
    return s.size();
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n = sizeof(a) / sizeof(a[0]);
    int k = 2;
 
    cout << sizeSubSet(a, k, n);
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
// Function to return the size of the required sub-set
static int sizeSubSet(int a[], int k, int n)
{
    // Sort the array
    Arrays.sort(a);
 
    // HashMap to store the contents
    // of the required sub-set
    HashMap< Integer, Integer> s = new HashMap< Integer, Integer>();
     
    // Insert the elements satisfying the conditions
    for (int i = 0; i < n; i++)
    {
        if (a[i] % k != 0 || s.get(a[i] / k) == null)
            s.put(a[i], s.get(a[i]) == null ? 1 : s.get(a[i]) + 1);
    }
 
    // Return the size of the set
    return s.size();
}
 
// Driver code
public static void main(String args[])
{
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n = a.length;
    int k = 2;
    System.out.println( sizeSubSet(a, k, n));
}
}
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
 
import math as mt
# Function to return the size of the required sub-set
def sizeSubSet(a, k, n):
 
    # Sort the array
    a.sort()
  
    # Set to store the contents of the required sub-set
    s=set()
  
    # Insert the elements satisfying the conditions
    for i in range(n):
        if (a[i] % k != 0 or a[i] // k not in s):
            s.add(a[i])
     
  
    # Return the size of the set
    return len(s)
 
  
# Driver code
a=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
n = len(a)
k = 2
 
print(sizeSubSet(a, k, n))
 
# This is contributed by Mohit kumar 29

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
     
// Function to return the size of
// the required sub-set
static int sizeSubSet(int []a, int k, int n)
{
    // Sort the array
    Array.Sort(a);
 
    // HashMap to store the contents
    // of the required sub-set
    Dictionary<int,
               int> s = new Dictionary<int,
                                       int>();
     
    // Insert the elements satisfying the conditions
    for (int i = 0; i < n; i++)
    {
        if (a[i] % k != 0 || !s.ContainsKey(a[i] / k))
        {
            if(s.ContainsKey(a[i]))
            {
                var val = s[a[i]];
                s.Remove(a[i]);
                s.Add(a[i], val + 1);
            }
            else
            {
                s.Add(a[i], 1);
            }
        }
    }
 
    // Return the size of the set
    return s.Count;
}
 
// Driver code
public static void Main(String []args)
{
    int []a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n = a.Length;
    int k = 2;
    Console.WriteLine(sizeSubSet(a, k, n));
}
}
 
// This code is contributed by PrinciRaj1992

<?php
// Php implementation of the approach
 
// Function to return the size of
// the required sub-set
function sizeSubSet($a, $k, $n)
{
 
    // Sort the array
    sort($a) ;
 
    // Set to store the contents of
    // the required sub-set
    $s = array();
 
    // Insert the elements satisfying
    // the conditions
    for ($i = 0 ; $i < $n ; $i++)
    {
        if ($a[$i] % $k != 0 or
            !in_array(floor($a[$i] / $k), $s))
            array_push($s, $a[$i]);
    }
     
    // Return the size of the set
    return sizeof($s);
 
}
 
// Driver code
$a = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10 );
$n = sizeof($a);
$k = 2;
 
echo sizeSubSet($a, $k, $n);
 
// This code is contributed by Ryuga
?>

<script>
 
// Javascript implementation of the approach
 
// Function to return the size of the
// required sub-set
function sizeSubSet(a, k, n)
{
     
    // Sort the array
    a.sort(function(a, b){return a - b;});
   
    // HashMap to store the contents
    // of the required sub-set
    let s = new Map();
       
    // Insert the elements satisfying the conditions
    for(let i = 0; i < n; i++)
    {
        if (a[i] % k != 0 ||
            s.get(a[i] / k) == null)
            s.set(a[i], s.get(a[i]) == null ?
                    1 : s.get(a[i]) + 1);
    }
   
    // Return the size of the set
    return s.size;
}
 
// Driver code
let a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
let n = a.length;
let k = 2;
 
document.write(sizeSubSet(a, k, n));
 
// This code is contributed by patel2127
 
</script>

6