#K56862. Construct Sequence from Powers of Two
Construct Sequence from Powers of Two
Construct Sequence from Powers of Two
You are given two positive integers n and s. Your goal is to determine whether it is possible to construct a sequence of n numbers, where each number is a power of two (with the smallest value being 2^0=1), such that the sum of the sequence is exactly s.
The minimum possible sum is achieved when every element is 1 (i.e. n), and the maximum sum is achieved when each element is the largest possible power of two in the sequence, which gives a sum of n\times 2^{n-1}. In other words, a valid sequence exists if and only if:
n\le s\le n\times 2^{n-1}
Determine whether s falls within this range (inclusive). If it does, output YES
; otherwise, output NO
.
inputFormat
The first line contains an integer t representing the number of test cases. Each of the next t lines contains two space-separated integers n and s.
outputFormat
For each test case, output a single line containing YES
if it is possible to construct the sequence with the sum s, or NO
otherwise.
4
3 12
4 16
2 1
5 31
YES
YES
NO
YES
</p>