Cacher is the code snippet organizer for pro developers

1 question

Good morning! Here's your coding interview problem for today.

This problem was asked by Nextdoor.

Implement integer division without using the division operator. Your function should return a tuple of (dividend, remainder) and it should take two numbers, the product and divisor.

For example, calling divide(10, 3) should return (3, 1) since the divisor is 3 and the remainder is 1.

Bonus: Can you do it in O(log n) time?

2 solution

def divide(a,b):

    shiftsize = 0
    val = a
    while val > b:
        shiftsize = shiftsize+1
        val = val >> 1
    
    shiftsize = shiftsize - 1
    count = 0
    num = a
    val = b
    while True:
        
        sub_val = b << shiftsize
        if num < sub_val:
            shiftsize = shiftsize -1
            continue
        num -= sub_val
        count = count + 1<<shiftsize
        if num < b:
            break
    
    print(count)
    print(num)


divide(17,3)