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
using System ; using System . Collections . Generic ; class GFG { static int findMaxLen ( int [ ] a , int k ) { int n = a . Length ; Array . Sort ( a ) ; bool [ ] vis = new bool [ n ] ; Dictionary < int , int > mp = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { mp . Add ( a [ i ] , i ) ; } int c = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( vis [ i ] == false ) { int check = a [ i ] * k ; if ( mp . ContainsKey ( check ) ) { c ++ ; vis [ mp [ check ] ] = true ; } } } return n - c ; } public static void Main ( String [ ] args ) { int K = 3 ; int [ ] arr = { 1 , 4 , 3 , 2 } ; Console . Write ( findMaxLen ( arr , K ) ) ; } }