Non Divisible Subsets - Hackerrank Problem Solution

 

Non Divisible Subsets

Hackerrank Problem Solution

PROBLEM STATEMENT

Given a set of distinct integers, print the size of a maximal subset of  where the sum of any  numbers in  is not evenly divisible by .

For example, the array  and . One of the arrays that can be created is . Another is . After testing all permutations, the maximum length solution array has  elements.

Function Description

Complete the nonDivisibleSubset function in the editor below. It should return an integer representing the length of the longest subset of  meeting the criteria.

nonDivisibleSubset has the following parameter(s):

• S: an array of integers
• k: an integer

Input Format

The first line contains  space-separated integers,  and , the number of values in  and the non factor.
The second line contains  space-separated integers describing , the unique values of the set.

Constraints

• All of the given numbers are distinct.

Output Format

Print the size of the largest possible subset ().

Sample Input

4 3
1 7 2 4

Sample Output

3

Explanation

The sums of all permutations of two elements from  are:

1 + 7 = 8
1 + 2 = 3
1 + 4 = 5
7 + 2 = 9
7 + 4 = 11
2 + 4 = 6

We see that only  will not ever sum to a multiple of .

---

SOLUTION

#!/bin/python3 # try a dumb bruteforce import sys from itertools import combinations def check_array(k, arr): for el1 in arr: test_arr = list(arr) test_arr.remove(el1) for el2 in test_arr: if (el1 + el2) % k == 0: return False return True def nonDivisibleSubset_brute(k, arr): if check_array(k, arr): return len(arr) best = 0 for num in range(1, len(arr)): to_remove = list(combinations(arr, num)) #print("to_remove = {}".format(to_remove)) for option in to_remove: test_arr = list(arr) #print("test_arr = {}".format(test_arr)) for el in option: test_arr.remove(el) if check_array(k, test_arr) == True: best = max(len(test_arr), best) return best def nonDivisibleSubset(k, arr): resid_cnt = [0] * k for el in arr: resid_cnt[el%k] += 1 res = min(1, resid_cnt[0]) for ind in range(1, (k//2)+1): if ind != k - ind: res += max(resid_cnt[ind], resid_cnt[k - ind]) if k % 2 == 0 and resid_cnt[int(k/2)] != 0: res += 1 return res if __name__ == "__main__": n, k = input().strip().split(' ') n, k = [int(n), int(k)] arr = list(map(int, input().strip().split(' '))) result = nonDivisibleSubset(k, arr) print(result)

Share Share Tweet Share Share Share

LIKE?

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.