algorithm - 检查给定值 AorB 和 APlusB 是否存在 A 和 B

Question

问题陈述:

给定两个非负整数:longs pairOr 和 pairSum。

确定是否有可能对于两个非负整数 A 和 B 我们都有:

• A 或 B = pairOr
• A + B = pairSum

上面的“或”表示按位或运算符。

如果我们能找到这样的 A 和 B，则返回 True，否则返回 False。

我的算法是这样的:

我采用了等式:A | B = X 和 A + B = Y,

现在从第二个方程中代入 A 的值后，(Y-B) | B=X.

我将从 0 遍历到 Y(代替 B)来检查上面的等式是否为真。

代码片段:

boolean isPossible(long orAandB,long plusAandB) {

    for(long i=0;i<=plusAandB;i++) {
        if(((plusAandB-i)|i)==orAandB ){
            return true;
        }
    }

    return false;

如果 plusAndB 的值是数字 10^18，它将给出 TLE。你能帮我优化一下吗？

Answer 1

您不需要完整的迭代，只需 O(N)。有一种方法可以在 O(logN) 中完成。

但是为您完全解决问题会带走大部分乐趣...;-)，所以这里是主要线索:

你的方程 (Y-B) | B= X 是一个很好的观察结果，第二个是从右边开始一点一点地看这个等式(这样你一开始就不必担心借位)。 Y、X 和 B 的哪些最后一位组合可以使你的等式成立？如果找到 B 位，如何继续递归地处理更高位(不要忘记减法可能需要借位)？我希望你记住二进制数减法的规则。

请记住，该问题仅要求真或假，而不要求任何特定的 A 或 B 值，可以节省指数级的复杂性。