Exactly Three Bits

AtCoder

IDarc161_b

Time2000ms

Memory256MB

Difficulty—

For a positive integer $X$, let $f(X)$ be the number of $1$s that appear when $X$ is represented in binary notation. For example, $6 = 110_{(2)}, \ 11 = 1011_{(2)}, \ 16 = 10000_{(2)}$, so $f(6) = 2, \ f(11) = 3, \ f(16) = 1$. You are given a positive integer $N$. Determine whether there is a positive integer $X$ less than or equal to $N$ such that $f(X) = 3$, and if so, find the maximum such $X$. There are $T$ test cases to solve. ## Constraints * $1 \leq T \leq 10^5$ * $1 \leq N \leq 10^{18}$ ## Input The input is given from Standard Input in the following format, where $N_i$ represents the value of $N$ in the $i$\-th test case: $T$ $N_1$ $N_2$ $\vdots$ $N_T$ [samples]

Samples

Input #1

4
16
161
4
1000000000000000000

Output #1

14
161
-1
936748722493063168

*   For the first test case, $f(14) = 3, \ f(15) = 4, \ f(16) = 1$, so the maximum positive integer $X$ satisfying $X \leq 16$ and $f(X) = 3$ is $14$.
*   For the second test case, $f(161) = 3$, so the maximum positive integer $X$ satisfying $X \leq 161$ and $f(X) = 3$ is $161$.
*   For the third test case, $f(1) = 1, \ f(2) = 1, \ f(3) = 2, \ f(4) = 1$, so there is no positive integer $X$ satisfying $X \leq 4$ and $f(X) = 3$.
*   As seen in the fourth test case, the input and output values may not fit in a 32-bit integer type.

API Response (JSON)

{
  "problem": {
    "name": "Exactly Three Bits",
    "description": {
      "content": "For a positive integer $X$, let $f(X)$ be the number of $1$s that appear when $X$ is represented in binary notation. For example, $6 = 110_{(2)}, \\ 11 = 1011_{(2)}, \\ 16 = 10000_{(2)}$, so $f(6) = 2, ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc161_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For a positive integer $X$, let $f(X)$ be the number of $1$s that appear when $X$ is represented in binary notation. For example, $6 = 110_{(2)}, \\ 11 = 1011_{(2)}, \\ 16 = 10000_{(2)}$, so $f(6) = 2, ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments