title: Find the largest subset of a set of numbers such that the sum of any 2 numbers is not divisible by a given number
body: <p>I'm trying to solve the Hackerrank problem <a href="https://www.hackerrank.com/challenges/non-divisible-subset?h_r=next-challenge&amp;h_v=zen" rel="nofollow noreferrer">Non-Divisible Subset</a> stated below:</p>
  
  <p><a href="https://i.stack.imgur.com/LYyCy.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/LYyCy.png" alt="enter image description here"></a></p>
  
  <p>I attempted the following solution (which works for the sample test case):</p>
  
  <pre><code># The lines below are for Hackerrank submissions
  # n, k = map(int, raw_input().strip().split(' '))
      # a = map(int, raw_input().strip().split(' '))
  
  n = 4
  k = 3
  a = [1, 7, 2, 4]
  
  while True:
      all_pairs = [(a[i],a[j]) for i in range(len(a)) for j in range(i+1,len(a))]
      tested_pairs = {pair: (pair[0] + pair[1]) % k != 0 for pair in all_pairs}
      disqualified_pairs = {key: value for key, value in tested_pairs.iteritems() if not value}.keys()
      if not disqualified_pairs:
          break
      occurrences = list(sum(disqualified_pairs, ()))
      counts = map(lambda x: occurrences.count(x), a)
      index_remove = counts.index(max(counts))
      a.remove(index_remove)
  
  print len(a)
  </code></pre>
  
  <p>What I'm trying to do is identify the 'offending' pairs and removing the element of <code>a</code> which occurs most frequently, until there are no 'offending' pairs left.</p>
  
  <p>However, I'm getting "RunTime Error" for most of the test cases:</p>
  
  <p><a href="https://i.stack.imgur.com/CnGiy.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/CnGiy.png" alt="enter image description here"></a></p>
  
  <p>Presumably the algorithm above works in this simple case where only one number (the number 2) needs to be removed, but fails in more complicated test cases. Can anyone see what is wrong with it?</p>
  
  <p><strong>UPDATE</strong></p>
  
  <p>Following poke's suggestion to test <code>k = 2</code> and <code>a = [1, 2, 3]</code>, I made the following modifications:</p>
  
  <pre><code>n = 4
  k = 2
  a = [1, 2, 3]
  
  while True:
      all_pairs = [(a[i],a[j]) for i in range(len(a)) for j in range(i+1,len(a))]
      disqualified_pairs = [pair for pair in all_pairs if (pair[0] + pair[1]) % k == 0]
      if not disqualified_pairs:
          break
      offending_numbers = sum(disqualified_pairs, ())   # 'Flatten' the disqualified pairs into a single list
      counts = {el: offending_numbers.count(el) for el in set(offending_numbers)}     # Count occurrences of each offending number
      number_to_remove = max(counts, key=counts.__getitem__)
      a.remove(number_to_remove)
  
  print len(a)
  </code></pre>
  
  <p>The resulting <code>a</code> is <code>[2, 3]</code> and contains two elements as expected. I've also checked that it still works for the original example. However, I am still getting a "Segmentation Fault" on some of the test cases:</p>
  
  <p><a href="https://i.stack.imgur.com/lJGjb.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/lJGjb.png" alt="enter image description here"></a></p>
  
  <p>According to <a href="https://www.hackerrank.com/challenges/pairs/forum/comments/9154" rel="nofollow noreferrer">https://www.hackerrank.com/challenges/pairs/forum/comments/9154</a>, segmentation faults typically occur because of invalid memory access (array indices which don't exist, etc.). I still haven't managed to find any other test cases, though, where the algorithm fails. Any ideas?</p>