[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.

Now to get the count, we look at each bit of a XOR b and a AND b one-by-one and multiply all possibilities. Note: a[i] is the i-th bit of a

• If a[i] XOR b[i] = 0 and a[i] AND b[i] = 0, then a[i] = b[i] = 0. Only one possibility for this bit.

• If a[i] XOR b[i] = 0 and a[i] AND b[i] = 1, then a[i] = b[i] = 1. Only one possibility for this bit.

• If a[i] XOR b[i] = 1 and a[i] AND b[i] = 0, then a[i] = 1 and b[i] = 0 or vice versa. Two possibilities.

• It's not possible to have a[i] XOR b[i] = 1 and a[i] AND b[i] = 1

Let’s take a simple example:

If the XOR is 5 and the SUM is 9 there are 4 pairs satisfying the SUM and XOR. They are (2, 7), (3, 6), (6, 3), (7, 2).

Converting to binary:

a XOR b = 5 = 101 (in binary) and a AND b = (9-5)//2 = 2= 010 (in binary).

Going bit by bit, we have the answer 2*1*2 = 4. This checks out with what we expected.

Let’s finally get to coding

def num_pairs(m, n):
    A = (m - n)//2
    xor_bits = bin(n)[2:] #Python's bin converts nums to binary with          #format 0bBINARY number
    and_bits = bin(A)[2:] #we just strip the 0b part
    
    max_len = max(len(xor_bits), len(and_bits))
    xor_bits = list(map(int, xor_bits.rjust(max_len, '0'))) #equalize lengths
    and_bits = list(map(int, and_bits.rjust(max_len, '0'))) 
    
    count=1
    for i in range(max_len):
        print(xor_bits[i], and_bits[i])
        if(xor_bits[i]==0):
            print("here")
            #only one possibbility either way. Multiplying by 1 is like doing nothing
            continue
        elif(and_bits[i]==0):
            print("double")
            count*=2
        else:
            #impossible
            print("terminate")
            return 0

    return count

Bonuses/Promotion (Get Free Stuff)

To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.

For most of my students, mock interviews have been very helpful. Enough mock interview practice is the key between getting that job offer and rejection. If you can get three people to become paying subscribers to this newsletter, you win a free mock interview. This offer has no upper limit, so the more subs you can get, the more mock interviews you win.

To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75