There are certain parts of a fence which need to be painted. Tom wants to divide work in such a way that each person gets exactly 1 contiguous part of the fence to paint.
Calculate number of ways in which Tom can divide the work. 2 ways are distinct if they don’t have exactly the same number of of pieces allocated.
Input:
n = Number of parts of fence
arr = State of the fence. 1 indicates that the part needs to be painted, 0 means it does not need to be painted.
Test Cases:
n = 5, arr = 10101
Output = 4
The ways to divide the fence are:
10|10|1
1|010|1
10|1|01
1|01|01
n = 2, arr = 00
Output = 0
The fence does not need any painting