我正在尝试解决如下所述的Hackerrank问题不可分割子集:
我尝试了以下解决方案(适用于示例测试用例):
# 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)
我要做的是确定“违规”对,并删除a
其中最频繁发生的元素,直到没有“违规”对为止。
但是,对于大多数测试用例,我都会遇到“运行时错误”:
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?
UPDATE
Following poke's suggestion to test k = 2
and a = [1, 2, 3]
, I made the following modifications:
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)
The resulting a
is [2, 3]
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:
According to https://www.hackerrank.com/challenges/pairs/forum/comments/9154, 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?
Instead of generating all pairs, this could be done by counting modulus.
Time Complexity: O(n + k)
Space Complexity: O(k) or O(1), because k is 100 at max, O(k) => O(1)
Basic idea
(a + b) % k = ((a % k) + (b % k)) % k
Since (a % k) is in range [0, k-1],
(a % k) + (b % k) is in range [0, 2k-2]
In addition,
(a + b) % k = 0 when
(a % k) = 0 and (b % k) = 0 OR
(a % k) + (b % k) = k
Main idea
根据以上信息,解决方案可能是
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句