Problem Statement
You have beads of several different colors that are to be placed on a string, with the requirement that for any group of three adjacent beads, all three must have different colors.
You are given a
Definition
- Class:
- StringBeads
- Method:
- numWays
- Parameters:
- int[]
- Returns:
- long
- Method signature:
- long numWays(int[] beads)
- (be sure your method is public)
Notes
- The resulting arrangement of beads is linear, not circular. (Thus, the first bead on the string, and the last, are not adjacent.)
Constraints
- beads will contain between 3 and 5 elements, inclusive.
- Each element of beads will be between 1 and 10, inclusive.
- The total number of beads will not exceed 35.
Examples
{ 1, 1, 1 }
Returns: 6
There are three beads, each a different color. The number of ways to arrange them is simply 3! = 6.
{ 1, 1, 1, 1 }
Returns: 24
Now with four beads, there are 4! = 24 arrangements.
{ 2, 1, 1 }
Returns: 2
Lets say that we have 2 green beads, 1 blue, and 1 red. In order to satisfy the requirement that each group of three consecutive beads have no two of the same color, the green beads must go at the beginning and end of the string. There are two ways to put the blue and the red in the middle: GRBG or GBRG.
{ 3, 1, 1 }
Returns: 0
There is no way to meet the requirement.
{ 3, 2, 2 }
Returns: 2
{7,7,7,7,7}
Returns: 1206522685040520
{10,10,10,5}
Returns: 84006840
{9,9,9,8}
Returns: 4976840082
{8,8,8,8,3}
Returns: 26582018108280
{1,2,3}
Returns: 0
{1,2,3,4}
Returns: 10
{1,2,3,4,5}
Returns: 13002
{5,4,3,2,1}
Returns: 13002
{9,8,7,6,5}
Returns: 137659322668468
{1,3,5,7,9}
Returns: 20760
{2,4,6,8,10}
Returns: 88358422
{10,10,10}
Returns: 6
{9,9,10}
Returns: 2
{4,5,7,3}
Returns: 588
{5, 3, 5, 10, 7 }
Returns: 1063713424
{7, 7, 7, 7, 7 }
Returns: 1206522685040520
{8, 6, 8, 6, 7 }
Returns: 513401645862496
{10, 8, 7, 5, 5 }
Returns: 18573355047042
{7, 7, 6, 7, 6 }
Returns: 114463568371380
{6, 7, 7, 7, 8 }
Returns: 786192615679824
{10, 10, 10, 5 }
Returns: 84006840
{5, 10, 7, 8, 5 }
Returns: 18573355047042
{5, 5, 5, 4, 4 }
Returns: 3364126704
{10, 10, 5, 6, 4 }
Returns: 760943909564
{6, 6, 6, 6, 6 }
Returns: 6577334442600