Programming Blog

Java Solution for finding Non Divisible Subset in Given Array Problem Description : Given a set of distinct integers, print the size of a maximal subset of S where the sum of any 2 numbers in S' is not evenly divisible by k. Example 1 : S = [19, 10, 12, 10, 24, 25, 22], k = 4 Output = 3 One of the arrays that can be created is S'[0] = [10, 12, 25] Another is S'[1] = [19, 22, 24]. After testing all permutations, the maximum length solution array has 3 elements. Example 2 : S = [1, 7, 2, 4], k = 3 Output = 3 [1, 7, 4] Example 3 : S = [278, 576, 496, 727, 410, 124, 338, 149, 209, 702, 282, 718, 771, 575, 436], k = 7 Output = 11 In simple word, we have to find maximum subset of current array where it can not be divisible by given k. Lets jump on code. Solution 1 : Java Solution for finding Non Divisible Subset in Given Array import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.funct