1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ ,Appreciate your answer. if you give any example, it would be better.Thanks. $\endgroup$ – tedd Nov 2 '19 at 11:41
  • $\begingroup$ I added an example. $\endgroup$ – Steven Nov 2 '19 at 13:25
  • $\begingroup$ Understood now :). However the time complexity would be log(d/x)?? $\endgroup$ – tedd Nov 2 '19 at 13:32
  • $\begingroup$ Yes, that's what I wrote. The number of iterations is proportional to the value of $k$, which is in $\Theta( \log \frac{d}{x})$ for arbitrary $x$ and $d$ with $x \le d$. However, since you restrict $d$ to be at most $2^{31}$, $k$ will always be at most $31$. $\endgroup$ – Steven Nov 2 '19 at 13:35
  • $\begingroup$ Thanks. I am posting another question to determine the time-complexity.Kindly check once (Similar to your solution). Link: cs.stackexchange.com/questions/116591/… $\endgroup$ – tedd Nov 2 '19 at 13:44
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To figure out the time complexity you just need to bound the value of variable $c$ at the end of the first loop. What is the value $x_c$ of $\texttt{x << c}$ after the $c$-th iteration of the first loop? What is the minimum value of $c$ such that the condition of the loop is not satisfied anymore, i.e., $x_c > dd$? $\endgroup$ – Steven Nov 3 '19 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.