PROBLEM STATEMENT
Let us consider a graph which consists of N vertices and some edges. No edge
connects a vertex to itself and there are no multiple edges allowed (that is,
given two vertices either there is one edge between them, or there are no edges).
The number of edges coming out of a vertex is called the degree of this vertex.
Your task is, given an int[] representing the list of degrees of a potential
graph, return the index of the degree which is the first obstruction to
building that graph. If there is no obstruction, return -1.
More precisely, consider a fixed input int[], say "degreesList". Let
degreesList have N elements. Call a graph G "i-good" if G has N vertices,
satisfies the conditions in the first paragraph, and i of its vertices have
degrees that are equal to the first i elements of degreesList. Your task is to
return the maximum i for which there is an i-good graph, or -1 if there is an
N-good graph (i.e. one whose vertices have the degrees given in degreesList).
NOTE:
- If we sum up all the degrees of a particular graph we would get an even
number as this sum is twice the number of edges (as we count each edge twice)
- In a graph with N vertices, the maximum possible degree for a vertex is N-1
(this number corresponds to a vertex which has edges to every other vertex)
- If a graph is "i-good" then it is also "k-good" for every k less than i
- The maximum i for which there is an "i-good" graph is the index of the first
degree that cannot be included in a graph
DEFINITION
Class: Graph
Method: badDegree
Parameters: int[]
Returns: int
Method signature (be sure your method is public): int badDegree(int[]
degreesList);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- degrees contains between 1 and 8 elements inclusive
- each element of degrees is between 0 and 10 inclusive
EXAMPLES
1. degreesList = {1,1,1,1,1} we can connect the first vertex to the second, and
the third to the fourth. There is no way to connect the last vertex then,
return 4
2. degreesList = {1,2,10,4,3} we can't have a degree equal to 10 in a graph
with 5 vertices, return 2
3. degreesList = {1} return 0
4. degreesList = {7,7,7,7,7,7,7,7} this is a complete graph with 8 vertices,
return -1
5. degreesList = {3,3,1,1} the first two vertices connect to all vertices,
hence the last two vertices should not have a degree less than 2, return 2
6. degreesList = {4,4,4,4,4,4,4,4} return -1
7. degreesList = {5,5,1,1,5,5,1,1} return 6