Divide Two Integers Without Using Multiplication, Division, and Mod operator LeetCode

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. If it is overflow, return MAX_INT.

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

 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.

Example 3:

Input: dividend = 0, divisor = 1
Output: 0

Example 4:

Input: dividend = 1, divisor = 1
Output: 1

NOTE:

• -231 <= dividend, divisor <= 231 - 1
• divisor != 0

This is very popular question in LeetCode and GeeksForGeeks A collection of hundreds of interview questions and solutions are available in our blog at Interview Question Solutions

---------------------------------------------------------
Solution:

Source code: Java

	/**
	* Divide two integers without using multiplication, division and mod operator.
	If it is overflow, return MAX_INT.
	*/
	package com.alg.leetcode;
	/**
	* @author rbaral
	*
	*/
	public class DivideTwoIntegers {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	int dividend =-100, divisor = 3;
	System.out.println(divide(dividend, divisor));
	}
	/**
	* divides two integers without using mul,division and mod operator
	* ref:http://www.programcreek.com/2014/05/leetcode-divide-two-integers-java/
	* @param dividend is the number that is being divided
	* @param divisor is the number which divides
	* @return
	*/
	public static int divide(int dividend, int divisor) {
	//base cases
	if(divisor==0) return Integer.MAX_VALUE;
	if(divisor==-1 && dividend == Integer.MIN_VALUE)
	return Integer.MAX_VALUE;
	//get long positive values
	long pDividend = Math.abs((long)dividend);
	long pDivisor = Math.abs((long)divisor);
	int result = 0;
	//repeat till the divisor at least equal to the dividend
	while(pDividend>=pDivisor){
	//calculate number of left shifts
	int numShift = 0;
	//figure out how many shifts are required to have divisor at least equal to the dividend
	while(pDividend>=(pDivisor<<numShift)){
	numShift++;
	}
	result += 1<<(numShift-1);
	//find out the dividend minus the largest shifted divisor
	pDividend -= (pDivisor<<(numShift-1));
	}
	if((dividend>0 && divisor>0) || (dividend<0 && divisor<0)){
	return result;
	}else{
	return -result;
	}
	}
	}

view raw DivideTwoIntegers.java hosted with ❤ by GitHub