Divide a number by 3 without using division, multiplication or modulus

Question

Without using /, % and * operators, write a function to divide a number by 3. itoa() is available.

The above was asked from me in an interview and I couldn't really come up with an answer. I thought of converting the number to a string and adding all the digits, but that will just tell me whether number is divisible or not. Or, by repeated subtraction it can also tell me the remainder. But, how do I obtain the quotient on division?

*how do I obtain the quotient on divison?* By counting (use `+`) the number of times you subtract ? — High Performance Mark, Jul 29 '15 at 14:23
See http://stackoverflow.com/questions/11694546/divide-a-number-by-3-without-using-operators for a bunch of solutions. (Some really creative) — Roger Lindsjö, Jul 29 '15 at 14:24
Itoa is in C++, but not in ANSI-C. Some compilers support it. Read more: http://www.cplusplus.com/reference/cstdlib/itoa/ — Totoo, Jul 30 '15 at 09:57
Possible duplicate of [Divide a number by 3 without using \*, /, +, -, % operators](https://stackoverflow.com/questions/11694546/divide-a-number-by-3-without-using-operators) — phuclv, Jul 06 '18 at 15:21
This question is not a duplicate because this one allows `+` and `-` so pertains perfectly to early CPUs. The other question makes it more of a game/puzzle by not allowing those. And vastly complicates the answers. — hippietrail, Nov 05 '22 at 10:18

Totoo · Answer 1 · 2015-07-29T14:30:08.763

1

According to itoa the number is integer.

int divide(int a, int b)
{
  int n=0;
  while(1)
  {
    a-=b;
    if(a<b)
    {
      n=n+1;
      return n;
    }
    else
     n=n+1;
  }
}

Just count how many times b in a by subtracting it

Edit: Removed the limit

edited Jul 29 '15 at 14:30

answered Jul 29 '15 at 14:28

Totoo

139
11

score 1 · Accepted Answer · answered Jul 29 '15 at 14:43

The below code takes in 2 integers, and divides the first by the second. It supports negative numbers.

int divide (int a, int b) {
    if (b == 0)
        //throw division by zero error

    //isPos is used to check whether the answer is positive or negative
    int isPos = 1;
    //if the signs are different, the answer will be negative
    if ((a < 0 && b > 0) || (a > 0 && b < 0))
        int isPos = 0;


    a = Math.abs(a);
    b = Math.abs(b);
    int ans = 0;
    while (a >= b) {
        a = a-b;
        ans++;
    }
    if (isPos)
        return 0-ans;
    return ans;
}

Douglas Zare · Answer 3 · 2015-07-29T23:15:33.257

The "count how many times you subtract 3" algorithm takes theta(|input|) steps. You could argue that theta(|input|) is fine for 32-bit integers, in which case why do any programming? Just use a lookup table. However, there are much faster methods which can be used for larger inputs.

You can perform a binary search for the quotient, testing whether a candidate quotient q is too large or too small by comparing q+q+q with the input. Binary search takes theta(log |input|) time.

Binary search uses division by 2, which can be done by the shift operator instead of /, or you can implement this yourself on arrays of bits if the shift operator is too close to division.

It is tempting to use the fact that 1/3 is the sum of the geometric series 1/4 + 1/16 + 1/64 + 1/256 + ... by trying (n>>2) + (n>>4) + (n>>6) + ... however this produces the wrong answer for n=3,6,7,9, 11, 12, 13, 14, 15, 18, ... It is off by two for n=15,30,31, 39, .... In general, this is off by O(log n). For n nonnegative,

(n>>2) + (n>>4) + (n>>6) + ...  = (n-wt4(n))/3

where wt4(n) is the sum of the base 4 digits of n, and the / on the right hand side is exact, not integer division. We can compute n/3 by adding wt4(n)/3 to (n>>2)+(n>>4)+(n>>6)+... We can compute the base 4 digits of n and therefore wt4(n) using only addition and the right shift.

int oneThirdOf(int n){
    if (0<=n && n<3)
        return 0;
    if (n==3)
        return 1;
    return sum(n) + oneThirdOf(wt4(n));
}

// Compute (n>>2) + (n>>4) + (n>>6) + ... recursively.
int sum(int n){
    if (n<4)
        return 0;
    return (n>>2) + sum(n>>2);
}

// Compute the sum of the digits of n base 4 recursively.
int wt4(int n){
    if (n<4)
        return n;
    int fourth = n>>2;
    int lastDigit = n-fourth-fourth-fourth-fourth;
    return wt4(fourth) + lastDigit;
}

This also takes theta(log input) steps.

Divide a number by 3 without using division, multiplication or modulus

3 Answers3