-
Notifications
You must be signed in to change notification settings - Fork 0
/
2017-zero-sum-sub-arrays.rb
93 lines (78 loc) · 1.83 KB
/
2017-zero-sum-sub-arrays.rb
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
# source: https://programmingpraxis.com/2017/10/13/zero-sum-sub-arrays/
#
# Zero-Sum Sub-Arrays
#
# This interesting little question comes from Career Cup:
#
# Given an array that contains only the elements -1 and 1, find the number of
# sub-arrays with a sum of zero. For instance, given the array [-1, 1, -1, 1],
# there are four sub-arrays that sum to zero:
# [-1, 1], [1, -1], [-1, 1] and [-1, 1, -1, 1].
#
# Your task is to count the sub-arrays of a -1/1 array that sum to zero. When
# you are finished, you are welcome to read or run a suggested solution, or to
# post your own solution or discuss the exercise in the comments below.
def zero_sum_sub_arrays(xs)
return 0 if xs.size < 2
(2..xs.size)
.flat_map { |n| xs.each_cons(n).to_a }
.select { |xs| xs.sum == 0 }
.size
end
# Test
5.times do |n|
[1, -1].repeated_permutation(n).map do |input|
puts "#{input} -> #{zero_sum_sub_arrays(input)}"
end
end
__END__
Solution in Ruby
[sourcecode lang="ruby"]
def zero_sum_sub_arrays(xs)
return 0 if xs.size < 2
(2..xs.size)
.flat_map { |n| xs.each_cons(n).to_a }
.select { |xs| xs.sum == 0 }
.size
end
# Test
5.times do |n|
[1, -1].repeated_permutation(n).map do |input|
puts "#{input} -> #{zero_sum_sub_arrays(input)}"
end
end
[/sourcecode]
produces:
[sourcecode]
[] -> 0
[1] -> 0
[-1] -> 0
[1, 1] -> 0
[1, -1] -> 1
[-1, 1] -> 1
[-1, -1] -> 0
[1, 1, 1] -> 0
[1, 1, -1] -> 1
[1, -1, 1] -> 2
[1, -1, -1] -> 1
[-1, 1, 1] -> 1
[-1, 1, -1] -> 2
[-1, -1, 1] -> 1
[-1, -1, -1] -> 0
[1, 1, 1, 1] -> 0
[1, 1, 1, -1] -> 1
[1, 1, -1, 1] -> 2
[1, 1, -1, -1] -> 2
[1, -1, 1, 1] -> 2
[1, -1, 1, -1] -> 4
[1, -1, -1, 1] -> 3
[1, -1, -1, -1] -> 1
[-1, 1, 1, 1] -> 1
[-1, 1, 1, -1] -> 3
[-1, 1, -1, 1] -> 4
[-1, 1, -1, -1] -> 2
[-1, -1, 1, 1] -> 2
[-1, -1, 1, -1] -> 2
[-1, -1, -1, 1] -> 1
[-1, -1, -1, -1] -> 0
[/sourcecode]