Nullify Prefix
Accenture coding challenges question, verified with a worked answer. Free to practise - no sign-up.
You are given an array arr of size N. You can change any element which is initially 0 to any arbitrary value. Your task is to maximize the number of indices i such that the prefix sum of the array up to index i is exactly 0.
Input format
The first line contains N, the size of the array. The second line contains N integers representing the array arr.
Output format
Return a single integer representing the maximum number of prefix sums that can equal 0.
Constraints
1 <= N <= 10^5
-10^9 <= arr[i] <= 10^9
Sample tests
Sample 1
Input
5
2 0 -1 1 0
Expected
3Sample 2
Input
4
0 1 0 0
Expected
4Sample 3
Input
4
1 1 1 1
Expected
0Show a reference solution
Reference solution
def solve_nullify(arr):
segments = []
current_seg = []
for x in arr:
if x == 0:
segments.append(current_seg)
current_seg = [0]
else:
current_seg.append(x)
segments.append(current_seg)
ans = 0
p = 0
for x in segments[0]:
p += x
if p == 0:
ans += 1
for seg in segments[1:]:
freq = {}
max_f = 0
for x in seg:
p += x
freq[p] = freq.get(p, 0) + 1
if freq[p] > max_f:
max_f = freq[p]
ans += max_f
return ans