Dividing 2 integers with some constraints

Question

This a problem i came across while practicing binary search. Here is the problem:

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero.

Note:

1. Both dividend and divisor will be 32-bit signed integers.
2. The divisor will never be 0.
3. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.

A Brute force Solution is that subtract the dividend with the divisor till it is greater and the number of subtractions is the result. But it is giving Time Limit Exceeding error.

How to solve the problem efficiently or using Binary Search ??

Also provide the time complexity as well.

Answer 1

Here is a strategy (I will only consider positive numbers): Let $d$ be the dividend and $x$ be the divisor. Generate all values $x_i = 2^i x$, up to some some $x_k$ such that $x_{k+1}$ exceeds the dividend. This can be done with only one addition per value since $x_{0} = x$ and, for $i \ge 1$, $x_i = x_{i-1} + x_{i-1}$. Similarly, generate all values $b_i = 2^i$ for $i=0, \dots, k$.

Let $r$ be a variable that will hold the result. Initially $r=0$. For $i=k$ down to $0$ do the following:

• Check whether $x_i$ is bigger than $d$;
• If that is the case, then you know that, by subtracting $x_i$ from $d$, you are effectively subtracting $x$ from $d$ a total of $b_i = 2^i$ times. Update $d = d- x_i$, and $r = r + b_i$.

Finally, return $r$.

This strategy requires only a logarithmic number of operations w.r.t. $d/x$ (up to multiplicative and additive constants). Since this is at most $2^{31}$, the time needed is always upper bounded by a constant.

---

As an example, let's divide $62$ by $3$. The sequences of values $x_i$ will be: $x_0 = 3, x_1 = 6, x_2 = 12, x_3 = 24, x_4 = x_k = 48$, since $x_5 = 96 > 62$. The corresponding values $b_i$ are: $b_0 = 1, b_1=2, b_2=4, b_3=8, b_4=16$.

• Initially $d=62$, $x=3$, $r=0$.

• In the fist iteration ($i=k=4$) we have $62 = d \ge 48 = x_4 $, and we update: $d = 62 - x_4 = 62-48 = 14$, and $r = 0 + b_4 = 0 + 16 = 16$.

• In the second iteration ($i=3$) we do nothing since $d = 14 \not\ge 24 = x_3$.

• In the third iteration ($i=2$) we have $d = 14 \ge 12 = x_2$, and we update $d = 14 - x_2 = 14 - 12 = 2$, and $r = 16 + b_2 = 16 + 4 = 20$.

• In the forth iteration ($i=1$) we do nothing since $d = 2 \not\ge 6 = x_1$.

• In the fifth and final iteration ($i=0$) we do nothing since $d = 2 \not\ge 3 = x_0$.

In the end we have $r=20$ and $d=2$. Indeed: $62 = 3 \cdot 20 + 2$.

Answer 2

With the help of Steven, i am posting the solution.

def divide(dd,dr):
    '''
            let dd and dr be the dividend and divisor
            x be the current macium divisor, less that dividend
            c be the counter
            q is the qutotient
    '''
    x=dr
    c=0
    while (x<<c) <= dd:
            c+=1
    print(c)
    q=0

    #then subtract from dividend and update result as usual manner

    #will run c time i.e lgx time  -----------Loop2
    for j in range(c-1,-1,-1):
            if x<<j <= dd :
                    dd-=(x<<j)
                    q+=1<<j


    print(q,dd)

    '''
    total time complexity will be 2lgx i.e lgx
    '''

** Just Little bit doubt in the time complexity of loop1 and loop2.**

But this solution works.

Answer 3

The best strategy when given a problem with stupid restrictions is to ignore the restrictions and write z = x / y. As it is, solving this problem doesn't help you understanding anything, and doesn't help you doing anything.