Largest possible Subset from an Array such that no element is K times any other element in the Subset | C ++ implementation of the above approach ; Function to find the maximum size of the required subset ; Size of the array ; Sort the array ; Stores which index is included or excluded ; Stores the indices of array elements ; Count of pairs ; Iterate through all the element ; If element is included ; Check if a [ i ] * k is present in the array or not ; Increase count of pair ; Exclude the pair ; Driver code
#include <bits/stdc++.h> NEW_LINE #define ll  long long NEW_LINE using namespace std ; int findMaxLen ( vector < ll > & a , ll k ) { int n = a . size ( ) ; sort ( a . begin ( ) , a . end ( ) ) ; vector < bool > vis ( n , 0 ) ; map < int , int > mp ; for ( int i = 0 ; i < n ; i ++ ) { mp [ a [ i ] ] = i ; } int c = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( vis [ i ] == false ) { int check = a [ i ] * k ; if ( mp . find ( check ) != mp . end ( ) ) { c ++ ; vis [ mp [ check ] ] = true ; } } } return n - c ; } int main ( ) { int K = 3 ; vector < ll > arr = { 1 , 4 , 3 , 2 } ; cout << findMaxLen ( arr , K ) ; }