Given am array of N integers is it possible to design a simple graph of N vertices?.
A graph considered simple if it has no self-loop r multi-edges. The condition is that each element of array should be used exactly once for degrees of vertices of the graph.
Print Yes if graph can be designed other wise no.
INPUT
A single integer T, in the first line, denoting the no. of test cases.
For each test case first line is a single integer N, denoting the no. of elements of an array A.
The second line contains N space separated integers denoting the elements of an array.
OUTPUT
For each test case print “YES” or “NO” without quotes.
SAMPLE INPUT
3
2
1 1
3
1 2 1
3
1 1 1
SAMPLE OUTPUT
YES
YES
NO
Please write the problem clearly. What does each element of the array signify?
@senbihan
It is the degree of each vertex.
@senbihan
I have updated the question look at it once more. Tell me if further clarification is needed.
I think this can be solved as follows :
- Since each element a[i] denotes the degree of the ith vertex we can say that the value of any a[i] can be at most n-1
- Secondly, we need to make sure that the sum of all elements in the array (i.e sum of all degrees) is a even number
If the above 2 conditions are met, then print YES, otherwise print NO
@ronakchauhan
How to deal with multi-edges. I think the approach which you proposed will not be able to handle multi-edges.
The question clearly stated that the graph should be a simple graph meaning no multi-edges and hence the 1st condition is valid.
If u still have doubts about it, try drawing a simple graph where you keep the degree of a vertex > |V|-1. (U will end up with a multigraph)
Edit : my solution in code [here][1]
[1]: https://pastebin.com/XGwDBFUK
I’ll give a hint for this problem 
For any graph G, SUM(Degree of each node) = 2 x Edges. Using this formula, you get the edges. So you have V,E. Is it possible to draw a Graph with V vertex and E edges, satisfying your constraints.
@ronakchauhan
what you said is wrong,for example consider the following case
1
4
3 3 1 1
For this input your code will print YES,but the answer is no
edges will be like this
1 2
1 3
1 4
2 2
There is a self loop for node 2 and hence answer is NO
Ohh i get it @hruday968, thanks for pointing out!
After some googling I found that this problem is the graph realization problem
with slight variation. It can be solved using Erdős–Gallai theorem.
One way to solve this would be to sort the array in descending order and then apply the theorem
Everyone should know the programming language in every sense of knowledge.wedding photography Kerala and the team like this article so much.
@hruday968
What would be the correct way then.