给定 N,return M 满足等式:N + M = 2 * (N XOR M)
Given N, return M that satisfy the equation: N + M = 2 * (N XOR M)
问题
Given N, return M that satisfy the equation: N + M = 2 * (N ^ M)
约束条件
1 <= Test Cases = 10^5;
1 <= N <= 10^18
我在一次招聘挑战中遇到了这个问题。
通过反复试验,我发现了一个模式 - 在 N/3 和 3N 之间存在这样一个 M,并且 N + M是偶数。因此,我将其编码并提交后,我的解决方案仅成功通过了一半的测试用例。这不是什么优化,因为此方法的时间复杂度与蛮力解决方案的时间复杂度相同。
我知道我的解决方案不是最优解。
这是我的解决方案:
def solve(n):
m = n//3
end = 3*n
# If both m and n are odd/even, their sum will be even
if (m&1 == 1 and n & 1 == 1) or (m&1 == 0 and n&1 == 0):
inc = 2
else:
m += 1
inc = 2
while m <= end:
if (n + m) == 2 * (n ^ m):
return m
m += inc
有人可以向我提供一些 hints/methods/algorithm 以获得最佳解决方案。谢谢!
m
的最低位已确定(因为 n+m
必须是偶数)。给定最低位,确定下一位,依此类推。
该观察导致这个 O(log n) 解决方案:
def solve(n):
b = 1
m = 0
while n + m != 2 * (n ^ m):
mask = 2 * b - 1
if ((n + m) & mask) != ((2 * (n ^ m)) & mask):
m += b
b *= 2
return m
实现这一点的另一种方法是找到 m+n
和 2*(n^m)
不同的最小位,并在 m
中切换该位。这导致了这个非常紧凑的代码(使用新的海象运算符和一些位技巧):
def solve(n):
m = 0
while r := n + m ^ 2 * (n ^ m):
m |= r & -r
return m
问题
Given N, return M that satisfy the equation: N + M = 2 * (N ^ M)
约束条件
1 <= Test Cases = 10^5;
1 <= N <= 10^18
我在一次招聘挑战中遇到了这个问题。
通过反复试验,我发现了一个模式 - 在 N/3 和 3N 之间存在这样一个 M,并且 N + M是偶数。因此,我将其编码并提交后,我的解决方案仅成功通过了一半的测试用例。这不是什么优化,因为此方法的时间复杂度与蛮力解决方案的时间复杂度相同。
我知道我的解决方案不是最优解。
这是我的解决方案:
def solve(n):
m = n//3
end = 3*n
# If both m and n are odd/even, their sum will be even
if (m&1 == 1 and n & 1 == 1) or (m&1 == 0 and n&1 == 0):
inc = 2
else:
m += 1
inc = 2
while m <= end:
if (n + m) == 2 * (n ^ m):
return m
m += inc
有人可以向我提供一些 hints/methods/algorithm 以获得最佳解决方案。谢谢!
m
的最低位已确定(因为 n+m
必须是偶数)。给定最低位,确定下一位,依此类推。
该观察导致这个 O(log n) 解决方案:
def solve(n):
b = 1
m = 0
while n + m != 2 * (n ^ m):
mask = 2 * b - 1
if ((n + m) & mask) != ((2 * (n ^ m)) & mask):
m += b
b *= 2
return m
实现这一点的另一种方法是找到 m+n
和 2*(n^m)
不同的最小位,并在 m
中切换该位。这导致了这个非常紧凑的代码(使用新的海象运算符和一些位技巧):
def solve(n):
m = 0
while r := n + m ^ 2 * (n ^ m):
m |= r & -r
return m