prathams's blog

Solving 2 equation
By prathams, history, 7 years ago, In English

Given x and y, we need to find smallest a and b such that
a + b = x
a xor b = y

How to solve this?

Tags xor
  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is it 1 ≤ x, y ≤ 107? If so, you can brute-force the value of a. If you decide the value of a, the value of b is determined to be x - a, and you can easily check a xor b.

But, I have two questions:
1. What is the actual constraints?
2. Smallest a and b? Which value should be minimized?

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it
Hint

By the way, I solved this question few months back and this is the code: https://ideone.com/WmTLgr

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Another way to solve this problem to simulate the process using digit DP, it works in O(logN).

→ Reply