fighterphoenix's blog

How to Solve this XOR Problem??
By fighterphoenix, history, 4 months ago, In English

You are given three integers $$$A$$$,$$$B$$$, and $$$C$$$, and your task is to apply bitwise XOR a number x on the $$$A$$$,$$$B$$$ and $$$C$$$ such that they transform into non-decreasing order? Also A, B, C, x lie in the range from 1 to 1e9.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by fighterphoenix (previous revision, new revision, compare).

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A^B will denote A XOR B operation. Consider the most significant bit in (B^C). If B > C, this bit must be set in x. If B < C, this bit must be unset in x. Do the same for A and B. If some bit in x must be set and unset at the same time, answer is -1, otherwise we can choose OR of bits that must be set.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is a follow up for the question also, that if there exists multiple solutions find the minimum value of x.

    Understood your logic and will be implementing it, Thanks for the help friend!

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In my approach, only those bits that must be set, are present in x, therefore x is minimal.

      → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks bro , your logic worked and that is a very good approach!

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Given A, B, C .. and you have to determine whether there is a number X such that if you set A:=A^X or B:=B^X or C:=C^X then you will have A<=B<=C ???? I couldn't understand what do you mean exactly ..

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, we have to set A:=A^X and B:=B^X and C:=C^X, then we need A<=B<=C, we have to find the value of x if it exists and if yes then print it else print -1.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      is it a codeforces problem???.. If so then can you send me the link? because I have a solution.. but am not sure about it..

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Actually it is a problem from GFG(www.geeksforgeeks.org) and unfortunately the problem is made to be private like only for those who have bought that course, but no worries, you can share your thoughts here, and we can discuss :)

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah ok .. my solution is that maybe you can split the problem into three subproblems: the first problem is that you have to find what is the smallest Y such that A^Y <= B^Y..

          The second is to find the smallest Z such that A^Z <= C^Z.. And the third is to find the smallest K such that B^K <= C^K..

          And the final X will be equal to (Y|Z|K) and then you check if it's valid or not.. I am not sure if it works or not .. but this may help you

          → Reply
          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            I will sure try this ,thanks for the effort friend!

            → Reply
          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
            ← Rev. 2   Vote: I like it +1 Vote: I do not like it

            It works, but we can take just x = (Y|K) and don't calculate Z at all, because if A^(Y|K) <= B^(Y|K) and B^(Y|K) <= C^(Y|K), A^(Y|K) <= C^(Y|K) holds.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              That's correct.. Actually I added Z just to make sure that A will be smaller than C because I couldn't find a proof for that..

              thanks for the proof :)

              → Reply