Paint Fence Work Split
Updated
Problem statement
A fence is made of n parts in a row, numbered 0 to n - 1. fence[i] = 1 means part i needs paint, and fence[i] = 0 means it does not.
The painting work is shared by cutting the fence between neighbouring parts into contiguous pieces, one piece per painter. A split is valid when:
- every part belongs to exactly one piece, and
- every piece contains exactly one part that needs paint.
Two splits are different when they cut the fence in different places.
Return the number of valid splits modulo 10^9 + 7. If no part needs paint, there is no valid split, so return 0.
Function
countFenceSplits(fence: int[]) → intExamples
Example 1
fence = [1,0,0,1,0,1]return = 6Parts 0, 3 and 5 need paint, so there are three pieces. The first cut must fall somewhere between parts 0 and 3: right after part 0, 1 or 2, which is 3 choices. The second cut must fall right after part 3 or part 4, which is 2 choices. That gives 3 * 2 = 6 splits:
1 | 001 | 011 | 0010 | 110 | 01 | 0110 | 010 | 1100 | 1 | 01100 | 10 | 1
Example 2
fence = [1,1,0,1]return = 2Parts 0 and 1 both need paint and sit next to each other, so a cut must go between them. The next cut goes right after part 1 or right after part 2. The two splits are 1 | 1 | 01 and 1 | 10 | 1. A piece such as 11 is not allowed because it holds two parts to paint.
Example 3
fence = [0,0,0]return = 0No part needs paint, so there is no way to give every piece exactly one part to paint. The answer is 0.
Example 4
fence = [0,1,0,0]return = 1Only part 1 needs paint, so the whole fence is one piece and there is exactly 1 way.
Constraints
1 <= fence.length <= 10^5fence[i]is0or1
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Get Triplet CountIBM · OAIBM interview questions
- Sum of Pipeline Response TimesBloomberg LP · OABloomberg LP interview questions
- Count Reverse-Digit PairsVisa · OAVisa interview questions
- Get Triplet CountPoint72 · OAPoint72 interview questions
- Product of Subset MaximaArcesium · OAArcesium interview questions
- Find Maximum Number of Balanced CombinationsAmazon · OA
- Counting Triplets Divisible by DAT&T · OAAT&T interview questions
- Count Valid TeamsWells Fargo · OAWells Fargo interview questions
- Next Pascal Row CoefficientIntuit · OAIntuit interview questions
- Minimum Operations to Flip Exactly K BitsGoogle · OAGoogle interview questions