Largest possible Subset from an Array such that no element is K times any other element in the Subset | Java 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
import java . util . * ; class GFG { static int findMaxLen ( int [ ] a , int k ) { int n = a . length ; Arrays . sort ( a ) ; boolean [ ] vis = new boolean [ n ] ; HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { mp . put ( 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 . get ( check ) ] = true ; } } } return n - c ; } public static void main ( String [ ] args ) { int K = 3 ; int [ ] arr = { 1 , 4 , 3 , 2 } ; System . out . print ( findMaxLen ( arr , K ) ) ; } }