B - Halving Subtraction Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

あなたは A に対して以下の操作を 0 回以上好きな回数行うことができます：

  • 正整数 x_0 を選び、x=x_0 とする。その後、i=1,2,\ldots,N の順に以下を行う：
    • A_i から x を引き、x を \displaystyle \left\lfloor \frac x2\right\rfloor で置き換える。

A の要素を全て 0 にすることが可能か判定し、可能な場合は全て 0 にするために必要な操作回数の最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\le T\le 10^4
  • 1\le N\le 30
  • 0\le A_i\le 10^9
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N
A_1 A_2 \ldots A_N

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

各テストケースについて、A の要素を全て 0 にすることが可能ならば必要な操作回数の最小値を、不可能ならば -1 を出力せよ。

入力例 1

4
2
10 4
2
0 1
3
0 0 0
5
16 7 2 1 0

出力例 1

2
-1
0
3

1 番目のテストケースについて考えます。

以下のように操作することで 2 回の操作で A の要素を全て 0 にすることができます：

  • x_0=3 を選ぶ。A=(10,4) から A=(7,3) となる。
  • x_0=7 を選ぶ。A=(7,3) から A=(0,0) となる。

2 回未満の操作で A の要素を全て 0 にすることはできないので、1 行目には 2 を出力してください。

Score : 500 points

Problem Statement

You are given a length-N sequence of non-negative integers A=(A_1,A_2,\dots,A_N).

You can perform the following operation on A any number of times, possibly zero:

  • Choose a positive integer x_0, and set x=x_0. Then, for i=1,2,\ldots,N in this order, do the following:
    • Subtract x from A_i, and replace x with \displaystyle \left\lfloor \frac x2\right\rfloor.

Determine whether it is possible to make all elements of A equal to 0, and if it is possible, find the minimum number of operations required to do so.

You are given T test cases; solve each of them.

Constraints

  • 1\le T\le 10^4
  • 1\le N\le 30
  • 0\le A_i\le 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
A_1 A_2 \ldots A_N

Output

Output the answers for the test cases in order, separated by newlines.

For each test case, if it is possible to make all elements of A equal to 0, output the minimum number of operations required to do so; if it is not possible, output -1.

Sample Input 1

4
2
10 4
2
0 1
3
0 0 0
5
16 7 2 1 0

Sample Output 1

2
-1
0
3

Consider the first test case.

By performing the operations as follows, you can make all elements of A equal to 0 in two operations:

  • Choose x_0=3. A=(10,4) becomes A=(7,3).
  • Choose x_0=7. A=(7,3) becomes A=(0,0).

It is impossible to make all elements of A equal to 0 in fewer than two operations, so output 2 on the first line.