問題一覧 > 通常問題

No.3276 Make Smaller Popcount

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 80
作問者 : yu23578 / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 12688 / 自分の提出
問題文最終更新日: 2025-09-18 21:32:11
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest オムニバス (順位表) の他の問題:

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$
$testcase_1$
$testcase_2$
$testcase_3$
$\vdots$
$testcase_T$
Here, $testcase_i$ represents the information of the $i$-th test case and is given in the following format.
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。