Question

Formatted question description: https://leetcode.ca/all/29.html

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

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹ − 1]. For this problem, if the quotient is strictly greater than 2³¹ - 1, then return 2³¹ - 1, and if the quotient is strictly less than -2³¹, then return -2³¹.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Constraints:

-2³¹ <= dividend, divisor <= 2³¹ - 1
divisor != 0

Algorithm

To perform Bit Manipulation, you can utilize another artifact bit. The algorithm operates as follows:

Check if the dividend is greater than or equal to the divisor. If it is, initialize a variable t to be equal to the divisor and a count variable p to 1.
While twice t is less than or equal to the dividend, double t, double p, and update the result.
Continue the above step until t is greater than the dividend.
Determine the sign of the result based on the signs of the dividend and divisor. Use a long integer type for calculations and multiply the result by the sign.
Handle special cases like when the divisor is 0 or the dividend is -2147483648 and the divisor is -1. For such cases, return INT_MAX.

Code

/*
 * converting int to larger size type like long, or BigInteger.
 * since overflow on -2147483648 must be handled
 */
public class Divide_Two_Integers {

	public static void main(String[] args) {
		Divide_Two_Integers out = new Divide_Two_Integers();
		Solution_recursion s = out.new Solution_recursion();


		System.out.println(s.divide(101, 10));
		System.out.println(s.divide(-2147483648, 2));
	}


    // @note: give up on bit operation, biggest issue is, bit and negative int are hard to handle
    public class Solution_bit_on_int {
        public int divide(int n, int dsor) {
            if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) {
                return Integer.MAX_VALUE;
            }

            // save operations
            if(dsor == 1) {
                return n;
            }
            if(dsor == -1) {
                return n * -1;
            }

            int flag = 1;
            if(n < 0) {
                flag *= -1;
                n *= -1; // @note: overflow... -2147483648/2
            }
            if(dsor < 0) {
                flag *= -1;
                dsor *= -1;
            }

            int count = 0;
            // while(n > 0) {
            //     n -= dsor;
            //     count++;
            // }

            // moving faster than above while
            while(n > 0 && n >= dsor) { // while(n > 0) { @note: I missed case: 1/2
                int shift = 0; // bit shift

	            /* @note: below bit operation causes issue.
	                        2147483647/1
	                        last loop, shift=31, dsor=1
	                        should not enter below while, but when divisor is 1 or 2 or 4, etc:

	                        1<<31=(-2147483648)
	                        2<<30=(-2147483648)
	                        4<<29=(-2147483648)

	                        so, originally I was using "(dsor << shift)" as probe to see if over divident
	                        then I change it to be an int, and add extra overflow check
	            */

                // while((dsor << shift) <= n) {
                while((dsor << shift) <= n) { //@note: <n is non-stop loop, should be <=n. eg. 1/1
                    n -= dsor << shift;
                    count += 1 << shift;

                    // check bit overflow
                    if((Integer.MAX_VALUE >> 1) <= (dsor << shift)) {
                        break;
                    }

                    shift++;
                }
            }

            return count * flag;
        }
    }


    public class Solution_recursion {

		int result = 0;
		/*
		 * my way of acceleration, increase step size each iteration,
		 *
		 * eg:
		 *
		 * 101 / 10:
		 * 		101 - 10*1 = 91
		 * 		91 - 10*2 = 71
		 * 		71 - 10*4 = 31
		 *
		 * now 31 is less then 10*8, count=1+2+4=7 ok, send to next recursion
		 *
		 * 31 / 10: and repeat above acceleration, start again from step=1
		 * 		31 - 10*1 = 21
		 * 		21 - 10*2 = 1
		 *
		 * now 1 is less than 10*4, this recurion count=1+2=3
		 *
		 * add up all count=7+3=10
		 */
	    public int divide(int dividend, int divisor) {

	        // convert to long
	        long n = (long)dividend;
	        long dsor = (long)divisor;

	        if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) {
	            return Integer.MAX_VALUE;
	        }

	        // save operations
	        if(dsor == 1) {
	            return (int)n;
	        }
	        if(dsor == -1) {
	            return (int)(n * -1);
	        }

	        int flag = 1;
	        if(n < 0) {
	            flag *= -1;
	            n *= -1; // @note: overflow... -2147483648
	        }
	        if(dsor < 0) {
	            flag *= -1;
	            dsor *= -1;
	        }

	        dfs(n, dsor);

	        return flag * result;
	    }

	    public void dfs(long n, long dsor) {

//	    	if(n <= 0) {
	    	if(n < dsor) { // @note: missed here, end condition is not n
	    		return;
	    	}

	    	int step = 1;

	    	while (n >= (dsor * step)) { // @Note: should be >= , eg: 2/2 = 1

	    		n -= (dsor * step);

	    		result += step;

	    		step *= 2; // acceleration of step size
	    	}

	    	// now start again with no acceleration dsor
	    	dfs(n, dsor);
	    }
	}

	// @note: just convert to long, and solution AC. But code is ugly...
	public class Solution {
	    public int divide(int nn, int ddsor) {

	        // convert to long
	        long n = (long)nn;
	        long dsor = (long)ddsor;

	        if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) {
	            return Integer.MAX_VALUE;
	        }

	        // save operations
	        if(dsor == 1) {
	            return (int)n;
	        }
	        if(dsor == -1) {
	            return (int)(n * -1);
	        }

	        int flag = 1;
	        if(n < 0) {
	            flag *= -1;
	            n *= -1; // @note: overflow... -2147483648
	        }
	        if(dsor < 0) {
	            flag *= -1;
	            dsor *= -1;
	        }

	        int count = 0;
	        // while(n > 0) {
	        //     n -= dsor;
	        //     count++;
	        // }

	        // moving faster than above while
	        while(n > 0 && n >= dsor) { // while(n > 0) { @note: I missed case: 1/2
	            int shift = 0; // bit shift

	            /* @note: below bit operation causes issue.
	                        2147483647/1
	                        last loop, shift=31, dsor=1
	                        should not enter below while, but when divisor is 1 or 2 or 4, etc:

	                        1<<31=(-2147483648)
	                        2<<30=(-2147483648)
	                        4<<29=(-2147483648)

	                        so, originally I was using "(dsor << shift)" as probe to see if over divident
	                        then I change it to be an int, and add extra overflow check
	            */

	            // while((dsor << shift) <= n) {
	            while((dsor << shift) <= n) { //@note: <n is non-stop loop, should be <=n. eg. 1/1
	                n -= dsor << shift;
	                count += 1 << shift;

	                // check bit overflow
	                if((Integer.MAX_VALUE >> 1) <= (dsor << shift)) {
	                    break;
	                }

	                shift++;
	            }
	        }

	        long result = count * flag;
	        if(result > Integer.MAX_VALUE) {
	            return Integer.MAX_VALUE;
	        } else if(result < Integer.MIN_VALUE) {
	            return Integer.MIN_VALUE;
	        } else {
	            return (int)result;
	        }

	    }
	}


	public class Solution_over_time_limit {
	    public int divide(int n, int dsor) {
	        if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) {
	            return Integer.MAX_VALUE;
	        }

	        int flag = 1;
	        if(n < 0) {
	            flag *= -1;
	            n *= -1;
	        }
	        if(dsor < 0) {
	            flag *= -1;
	            dsor *= -1;
	        }

	        int count = 0;
	        while(n > 0) {
	            n -= dsor;
	            count++;
	        }

	        return count * flag;
	    }
	}

}

############

class Solution {
    public int divide(int a, int b) {
        int sign = 1;
        if ((a < 0) != (b < 0)) {
            sign = -1;
        }
        long x = Math.abs((long) a);
        long y = Math.abs((long) b);
        long tot = 0;
        while (x >= y) {
            int cnt = 0;
            while (x >= (y << (cnt + 1))) {
                cnt++;
            }
            tot += 1L << cnt;
            x -= y << cnt;
        }
        long ans = sign * tot;
        if (ans >= Integer.MIN_VALUE && ans <= Integer.MAX_VALUE) {
            return (int) ans;
        }
        return Integer.MAX_VALUE;
    }
}

// OJ: https://leetcode.com/problems/divide-two-integers/
// Time: O(logD) where D is |dividend|
// Space: O(1)
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (!divisor) return 0;  // divide-by-zero error
        bool pos1 = dividend > 0, pos2 = divisor > 0, pos = !(pos1^pos2);
        if (pos1) dividend = -dividend;
        if (pos2) divisor = -divisor;
        int q = 0, d = divisor, t = 1;
        while (t > 0 && dividend < 0) {
            if (dividend - d <= 0) {
                dividend -= d;
                q -= t;
                if ((INT_MIN >> 1) < d) {
                    t <<= 1;
                    d <<= 1;  
                }           
            } else {
                d >>= 1;
                t >>= 1;
            }
        }
        return pos? -q : q;
    }
};

class Solution:
    def divide(self, a: int, b: int) -> int:
        INT_MAX = (1 << 31) - 1
        INT_MIN = -(1 << 31)
        sign = -1 if a * b < 0 else 1
        a = abs(a)
        b = abs(b)
        tot = 0
        while a >= b:
            cnt = 0
            while a >= (b << (cnt + 1)):
                cnt += 1
            tot += 1 << cnt
            a -= b << cnt
        return sign * tot if INT_MIN <= sign * tot <= INT_MAX else INT_MAX

############

class Solution(object):
  def divide(self, dividend, divisor):
    """
    :type dividend: int
    :type divisor: int
    :rtype: int
    """
    if divisor == 0:
      return 0x7fffffff
    sign = 1
    if dividend * divisor < 0:
      sign = -1
    ans = 0
    cnt = 1
    dividend = abs(dividend)
    divisor = abs(divisor)
    subsum = divisor
    while dividend >= divisor:
      while (subsum << 1) <= dividend:
        cnt <<= 1
        subsum <<= 1
      ans += cnt
      cnt = 1
      dividend -= subsum
      subsum = divisor
    return max(min(sign * ans, 0x7fffffff), -2147483648)

func divide(a int, b int) int {
	sign, ans, INT32_MAX, INT32_MIN, LIMIT := false, 0, 1<<31-1, -1<<31, -1<<31/2
	if (a > 0 && b < 0) || (a < 0 && b > 0) {
		sign = true
	}
	a, b = convert(a), convert(b)
	for a <= b {
		cnt := 0
		// (b<<cnt) >= LIMIT 是为了避免 b<<(cnt+1) 发生溢出
		for (b<<cnt) >= LIMIT && a <= (b<<(cnt+1)) {
			cnt++
		}
		ans = ans + -1<<cnt
		a = a - b<<cnt
	}
	if sign {
		return ans
	}
	if ans == INT32_MIN {
		return INT32_MAX
	}
	return -ans
}

func convert(v int) int {
	if v > 0 {
		return -v
	}
	return v
}

public class Solution {
    public int Divide(int dividend, int divisor) {
        return (int)DivideInternal(dividend, divisor);
    }
    
    public long GetHighestBit(long x)
    {
        if (x == 0) return 0;
        long k = 0x80000000;
        while ((x & k) == 0)
        {
            k >>= 1;
        }
        return k;
    }

    public long DivideInternal(long dividend, long divisor)
    {
        int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
        if (dividend < 0) dividend = -dividend;
        if (divisor < 0) divisor = -divisor;
        
        long result = 0;
        long pointer = GetHighestBit(dividend);
        long currentHeader = 1; 
        dividend = dividend ^ pointer;
        while (pointer > 0)
        {
            result <<= 1;
            if (currentHeader >= divisor)
            {
                ++result;
                currentHeader -= divisor;
            }
            pointer >>= 1;
            bool nextIsOne = (dividend & pointer) != 0;
            currentHeader = (currentHeader << 1) + (nextIsOne ? 1 : 0);
            dividend = dividend ^ (nextIsOne ? pointer : 0);
        }
        
        result = sign * result;
        
        if (result > int.MaxValue || result < int.MinValue)
        {
            return int.MaxValue;
        }
        return result;
    }
}

29 - Divide Two Integers

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions