Menu Close

Arrange numbers in a circle so that any two neighbouring numbers differ by 1

One day Anna got the following task at school: to arrange several numbers in a circle so that any two neighboring numbers differs exactly by 1.
Anna was given several numbers and arranged them in a circle to fulfill the task.
Then she wanted to check if she had arranged the numbers correctly, but at this point her younger sister Maria came and shuffled all numbers. Anna got sick with anger but what’s done is done and the results of her work had been destroyed.
But please tell Anna: could she have hypothetically completed the task using all those given numbers?

Input:
The first line contains integer n — how many numbers Anna had ().

The next line contains those numbers, separated by a space. All numbers are integers and belong to the range from 1 to 109.


Output:
Print the single line "YES" (without the quotes), if Anna could have completed the task correctly using all those numbers (using all of them is necessary).
If Anna couldn't have fulfilled the task, no matter how hard she would try, print "NO" (without the quotes).

#include <stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
 return (*(int*)a -*(int*)b);
}
int main()
{int N,i;
  scanf("%d",&N);
  int *aa=(int*)malloc(N*sizeof(int));
  for(i=0;i<N;i++)
  scanf("%d",aa+i);
  qsort(aa,N,sizeof(int),cmp);
  N--;
  if((aa[N]-aa[0])>2)
  printf("NO");
  else
  printf("YES");
return 0;
}


INPUT_1:
7
3  4  5  2  3  4  5

OUTPUT:
NO


INPUT_2:
6
1  1  2  2  2  3

OUTPUT:
YES


ILLUSTRATION

Executed using gcc

Morae Q!