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.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
2 | cry | 160 |
4 | nor | 156 |
4 | atcoder_official | 156 |
6 | -is-this-fft- | 155 |
7 | adamant | 153 |
7 | maroonrk | 153 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
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.
Name |
---|
Auto comment: topic has been updated by fighterphoenix (previous revision, new revision, compare).
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.
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!
In my approach, only those bits that must be set, are present in x, therefore x is minimal.
Thanks bro , your logic worked and that is a very good approach!
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 ..
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.
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..
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 :)
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
I will sure try this ,thanks for the effort friend!
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.
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 :)