## Google Interview Question

Software Developers**Country:**United States

**Interview Type:**In-Person

I would suggest doing something like this...

1 send the ans, arr, index and current ans recursively

2 the good thing about using recursion is it reduces complexity of the idea

3 using OR '|' operator ensures that the program does not compute

through all combinations since it greedily returns true if it encounters a true

midway without processing the rest of the code

```
private static boolean isMgic(int ans, int[] arr)
{
return isMgic(ans, arr, 0, 0);
}
private static boolean isMgic(int ans, int[] arr, int index, int tmp)
{
if (arr.length > index)
return (isMgic(ans, arr, index + 1, tmp + arr[index])
| isMgic(ans, arr, index + 1, tmp - arr[index]));
if (ans == tmp)
return true;
return false;
}
```

I came up with this:

```
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 see wikipedia 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(n): # O(N)
if i - check_list[j] >= 0:
table[i, j + 1] = table[i, j] or table[i - check_list[j], j]
else:
table[i, j + 1] = table[i, j]
return table[target, n]
```

I came up with this using Python

```
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 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(n): # O(N)
if i - check_list[j] >= 0:
table[i, j + 1] = table[i, j] or table[i - check_list[j], j]
else:
table[i, j + 1] = table[i, j]
return table[target, n]
```

The 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]
```

leetcode 494.

- tyler_ua July 11, 2018take a look on the 282 - similar