题目描述
难度分:1100
输入T(≤2000)表示T组数据。每组数据输入x(2≤x≤109)。
找到一个严格小于x的正整数y,满足x、y和x⊕y组成一个(非退化的)三角形的三条边。
输出任意满足要求的y。如果y不存在,输出−1。
输入样例
7
5
2
6
3
69
4
420
输出样例
3
-1
5
-1
66
-1
320
算法
构造
不知道怎么做,但是观察case感觉如果x的二进制表示中没有0(比如x=3)或者只有一个1(比如x=2)应该是无解的。而对于一般情况,尝试了一下仅交换x二进制表示中第一对相邻的10
(从高位往低位)构造出y,结果发现刚好可以满足条件,所以尝试了提交,结果就过了。
复杂度分析
时间复杂度
每个case相当于只需要遍历x的每个二进制位,首先遍历一遍所有的二进制位确定其中1的个数,接下来再遍历一遍交换第一组相邻的10
,时间复杂度为O(log2x)。因此,处理全部T个case的总时间复杂度为O(Tlog2x)。
空间复杂度
每个case需要把x的各个二进制位存下来,依照这个二进制串来构造答案,因此额外空间复杂度为O(log2x)。
python 代码
t = int(input())
for _ in range(t):
x = int(input())
s = bin(x)[2:]
if s.count('1') == 1 or s.count('0') == 0:
print(-1)
else:
b = list(s)
n = len(b)
for i in range(1, n):
if b[i - 1] != b[i]:
b[i - 1], b[i] = b[i], b[i - 1]
break
print(int(''.join(b), 2))