No.3276 Make Smaller Popcount
Problem Statement
Given a positive integer $N$, determine whether there exists a positive integer $x$ satisfying $\mathrm{popcount}(N) > \mathrm{popcount}(N+x)$
and, if one exists, report its minimum value.
You are given $T$ test cases; solve each of them.
What is $\mathrm{popcount}$?
$\mathrm{popcount}(x)$ denotes the number of $1$s that appear when $x$ is written in binary. For example, since $13=1101_{(2)}$, we have $\mathrm{popcount}(13) = 3$.Constraints
・$1 \le T \le 2 \times 10^5$
・$1 \le N < 2^{30}$
・All input values are integers
Input
The input is given from standard input in the following format.$T$Here, $testcase_i$ represents the information of the $i$-th test case and is given in the following format.
$testcase_1$
$testcase_2$
$testcase_3$
$\vdots$
$testcase_T$
$N$
Output
Print $T$ lines. On the $i$-th line, for the $i$-th test case, print the minimum value if an $x$ satisfying the condition exists, and print -1 if none exists.
Sample
Sample 1
Input
3
5
7
12
Output
3
1
4
For the first test case:
When $x=1$, $\mathrm{popcount}(N) = 2 \le \mathrm{popcount}(N+x) = 2$, so it does not satisfy the condition.
When $x=2$, $\mathrm{popcount}(N) = 2 \le \mathrm{popcount}(N+x) = 3$, so it does not satisfy the condition.
When $x=3$, $\mathrm{popcount}(N) = 2 > \mathrm{popcount}(N+x) = 1$.
Therefore, print $x = 3$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。