Problem Statement
A group of n thieves needs some software to help them divide up their loot.
A necklace must be divided up as evenly as possible among the gang members.
The necklace is a circle of gems of different values.
The requirement is that the necklace be divided into n segments by cutting the necklace in n places. Every segment must contain at least one gem. The "inequity" of the division is the value of the most-valuable segment minus the value of the least-valuable segment. (The value of a segment is the sum of the values of the gems in that segment.) We want to minimize the inequity.
Create a class Necklaces that contains a method inequity that is given as input n and a int[] gems (the values of each gem in the necklace in order). The gems are in a circle, so the last element of gems is connected to the first element. The method should find the best way to divide the necklace and return the minimum possible inequity.
Definition
- Class:
- Necklaces
- Method:
- inequity
- Parameters:
- int, int[]
- Returns:
- int
- Method signature:
- int inequity(int n, int[] gems)
- (be sure your method is public)
Constraints
- n will be between 1 and 50 inclusive.
- gems will contain between n and 50 elements inclusive.
- Each element of gems will be between 1 and 100,000 inclusive.
Examples
1
{5,12,2,9}Returns: 0
Cut it once anywhere. There is only one segment, and its value if 28. The difference between the worst and best segment is 0 (28 - 28).2
{5,12,9,2}Returns: 4
Cut it between the 5 and 12, and also between the 12 and 9. The two resulting segments have values 12 and 9+2+5=16.4
{100,92,133,201,34,34,34,94,108}Returns: 29
Divide it as follows: 108 100 | 92 133 | 201 | 34 34 34 94. Then the result is 225 - 196.
Back to all problems