forked from anubhab91/CodeForces-5
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNon_Zero.py
More file actions
67 lines (41 loc) · 1.65 KB
/
Non_Zero.py
File metadata and controls
67 lines (41 loc) · 1.65 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
__author__ = 'Devesh Bajpai'
'''
https://codeforces.com/problemset/problem/1300/A
Solution: Interesting problem with few cases to handle.
Lets have totalNoOfZeroes capture the total no. of zeroes in the array, sum as sum and ans as total no. of operations
needed
We iterate over the numbers and calculate totalNoOfZeroes and sum.
Now, if the totalNoOfZeroes is 0, it means product would be non-zero. Hence we only need to concern about the sum being
zero. So we check that and if so, we add 1 to the ans since that 1 operation would add one and make the sum non-zero.
If the totalNoOfZeroes is not 0, it means the product is already zero. That means, we will have to do totalNoOfZeroes
operations to make those zeroes are ones to make the product non-zero. While doing that, we increased the sum by that,
hence we add totalNoOfZeroes to sum. Now the sum might be zero, if so we need to do one more operation to make it non
zero. Hence we add 1 to the ans. Else we already have the ans correct.
Finally we return the answer.
Time Complexity: O(n)
'''
def solve(t, nums):
totalNoOfZeroes = sum = ans = 0
ans = 0
for num in nums:
sum += num
if num == 0:
totalNoOfZeroes += 1
if totalNoOfZeroes == 0:
if sum == 0:
ans = 1
else:
ans = totalNoOfZeroes
sum += totalNoOfZeroes
if sum == 0:
ans += 1
return ans
if __name__ == "__main__":
n = int(raw_input())
answers = []
for i in xrange(0,n):
t = int(raw_input())
nums = map(int, raw_input().split(" "))
answers.append(solve(t, nums))
for answer in answers:
print answer