AorBとAPlusB

Question

問題文：long型pairOrとpairSum：

次の2つの非負整数を与えています。

は、2非負整数AとBのために、我々は両方持っている可能性があるかどうかを確認します。

• AまたはB = pairOr
• A + B = pairSum
上記

、 「または」はビット単位またはオペレータを示す。

このようなAとBが見つかるとTrueを返し、そうでなければFalseを返します。 | A：私は式を撮影した

：

私のアルゴリズムは、このように書きますB = X、A + B = Y、

ここで、第2式のAの値を代入した後、（Y-B）| B = X.

私は上記の式が真であるかどうかを調べるために0からY（Bの代わりに）までトラバースするつもりです。

コードスニペット：plusAndBの値は数10^18であれば

boolean isPossible(long orAandB,long plusAandB) { 

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

    return false; 

それはTLEを与えるだろう。最適化にお役立てください。

Answer 1

あなたは完全な反復を必要とせず、O（N）を与えます。 O（logN）でそれを行う方法があります。

しかし、あなたは楽しみのほとんどを奪うために、完全に問題を解決する... ;-)ので、ここでの主な手がかりです：

あなたの方程式(Y-B) | B= Xが一つの大きな観測され、第二の外観を持つことですこの方程式では、右から順に（ビットを借りることについて心配する必要はありません。 Y、X、Bの最後のビットの組み合わせによって、あなたの方程式は真となりますか？ Bビットが見つかった場合、どのように上位ビットを使って再帰的に続けるのですか（減算には借用が必要かもしれないことを忘れないでください）？バイナリ数値を減算するルールを覚えていれば幸いです。

この問題は、特定のAまたはBの値ではなく、真または偽を求めるだけであることに留意し、指数関数的な複雑さを軽減できます。