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 selfloop r multiedges. 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 asked 13 May '17, 11:57

The question clearly stated that the graph should be a simple graph meaning no multiedges 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 > V1. (U will end up with a multigraph) Edit : my solution in code here answered 14 May '17, 10:30

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 answered 15 May '17, 00:01

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 answered 15 May '17, 06:37

Everyone should know the programming language in every sense of knowledge.wedding photography Kerala and the team like this article so much. answered 15 May '17, 14:22

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.