This Diwali, Chef has decided to treat himself to a laddu feast. Chef's friends brought him some laddus, which he stored in an array A. It is guaranteed that the length of A is a power of 2. The ith element of the array A is a laddu of size Ai. Chef would like to eat every laddu, but sadly he is on a diet and is allowed to eat only one laddu. He came up with a novel way to resolve this problem. Chef performs the following steps in order: First, he pairs up every laddu from A with some other laddu - if there are N laddus in A, exactly N/2 pairs are created, with each laddu being in exactly one of the pairs. Further, every pair (x,y) must satisfy the condition |x−y|≤1; in other words, the sizes of the laddus in each pair cannot differ by more than 1. Next, for each pair of laddus (x,y) formed in step 1, mash them together to form a new laddu of size x+y. At the end of this process, Chef is left with exactly N/2 laddus. Repeat the process with the N/2 laddus he now has. At any point in time, if Chef is unable to form N/2 pairs (either because N=1, or because there is no way to pair up laddus satisfying the condition on their sizes) he will immediately stop the process. If there is only one laddu left in A when the process stops, Chef considers his efforts to be a success; else he considers it a failure. Print "YES" if there is a way for Chef to achieve success, else print "NO".
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m, n, T;
cin>>T;
while(T--){
cin >> m;
n = pow(2, m);
vector<int> v;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
v.push_back(x);
}
int min = *min_element(v.begin(), v.end());
int max = *max_element(v.begin(), v.end());
if (max - min <= 1)
{
cout << "YES" << endl;
}
else
cout << "NO"<<endl;
}
return 0;
}
