Flint
BAN USERThe optimal solution should be the one using pseudo-polynomial algorithm for the partition problem. Hope this is correct:
def is_magic(seq, magic_number):
# sum(seq) = sum_pos + sum_neg
# if there is a solution:
# sum_positive - sum_negative = magic_namber
# Therefore, the task can be formulated as looking for a subset of seq such that:
# sum_neg = (sum(seq) - magic_number)/2
check_list = seq[1:] # The first element of seq cannot be negative
tmp = sum(seq) - magic_number
if tmp % 2 != 0 or tmp < 0:
return False
# pseudo-polynomial algorithm for the partition problem
target = tmp // 2
n = len(check_list)
table = np.zeros((target + 1, n + 1), dtype=bool)
table[0, :] = True
for i in range(1, target + 1): # O(target)
for j in range(1, n + 1): # O(N)
if i - check_list[j - 1] >= 0:
table[i, j] = table[i, j - 1] or table[i - check_list[j - 1], j - 1]
else:
table[i, j] = table[i, j - 1]
return table[target, n]
This algorithm consists of:
(1) checking the least frequent element of a in b
(2) find all the occurrences of this in b
(3) from each position look left and right to see if there are other contiguous characters from a
- Flint October 15, 2018