[Solution]Problem 22: Positive Pairs meeting conditions[Jane Street]
Bitwise operations, Binary, Memory, Logical Operations, XOR, Math
Problem
This problem was asked by Jane Street.
Given integers M
and N
, write a program that counts how many positive integer pairs (a, b)
satisfy the following conditions:
a + b = M
a XOR b = N
Solution
To those of you unfamiliar with the XOR operator, it works as follows:
When the two elements we XOR have the same value in the place, the value of that place becomes 0. Otherwise, it becomes 1. The best description I have heard of it is addition without the carryover. Let’s take a few simple examples:
1^1=0
0^0=0
1^0=1
1^0^1^0=1^(0^1^0)=1^(0^(1^0))= 1^(0^1)= 1^1= 0
Since all the subscribers to my newsletter have a very high IQ, I don’t need to keep harping on. This is a great extended video for those interested
There is a relatively straightforward solution. We simply evaluate every possible pair of positive integers that can sum up to M
, and check whether they XOR
to N
. Since we only want positive numbers, the maximum number we want to check up to is M//2 (// is the integer division symbol).
def num_pairs(m, n):
count=0
for i in range(m // 2):
if i ^ (m - i) == n: #remember that i + m-i = m
count+=1
return count*2 (to account for both x,y and y,x pairs )
This will run in O(M)
time and require O(1)space.
Optimizing
The presence of the XOR operation hints at a more optimal solution. The first thing to do is to start viewing a and b in binary terms. Instead of a=4, we now see a=100. If you don’t understand binary number system, this is a quick intro. Take this as an interview tip: whenever we see Logical Operators, you mind should switch to Binary. It makes life easier.
Now is where we pull out the Math. Remember how we said that the XOR is addition without the carryover? This means that we can rephrase addition as the follow
a + b = a^b + 2* carryover(a,b)
where carryover (a,b) would just be the carryover of a+b. So the carryover(1,1) would be 1 (in binary). In our number system, the carryover(9,3) is 1 (since 9+3 is 12). Why do we do 2*carryover, instead of just adding the carry as is? Fantastic question.
Binary is a base 2 number system. Therefore, every carryover in Binary is worth two times the numerical value it represents. A carryover of 1 in the two’s place represents a value of 2, and so on (remember how we use the ten’s/hundreds/etc place in real life).
Now we substitute the values we have from the conditions
a+b = M
a^b = N
M= N+ 2* carryover(a,b) (substituting the values above)
=> carryover(a,b)= (M-N)/2
This is basic algebra. Take a second to convince yourself this is correct. If any of this is too hard, reach out to me and we can discuss it.
Figure out the carryover
Now we just need to figure out what the carryover should be. We know that carry(1, 1) will give us a carry of 1.carry(0,0) and carry(1,0) will return 0. This sounds like a familiar function. Yes it is the and (&) operator. For all possible values, a&b will return the same as carry(a,b). Thus we can equate the two. We have thus proved that
a&b= (M-N)/2
By representing things as logical operators and binary, we can now make optimizations. Remember that since M and N are in binary, we use should use a list representing the bits. So 10001 would be represented by a list [1,0,0,0,1].
We’re done with the Math. Now we will simply perform an analysis on the possible configs that our values can take and what that would mean for the result. This will allow us to cut down to logarithmic time.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.