29. Divide Two Integers
Problem Description
The problem at hand requires us to divide two integers, dividend
and divisor
, without using multiplication, division, and mod operator. The result should be the integer part of the quotient, with the division result truncated towards zero, meaning that any fractional part is disregarded. This operation should be handled with care as the problem also specifies dealing with overflows by capping the return value at 32-bit signed integer limits.
In essence, we are to implement a form of division that replicates how integer division works in programming languages where the result is truncated towards zero, ensuring we work within the 32-bit integer range. We have to be cautious, as the direct operations that normally achieve this (/, *, %) are not permitted.
Intuition
The solution relies on the concept of subtraction and bit manipulation to accomplish the division. Since we can't use the division operator, we think about what division actually means. Division is essentially repeated subtraction. For instance, when we say 10 divided by 2, it means how many times we can subtract 2 from 10 until we reach a number less than 2.
The intuition behind the solution is to use a subtraction-based approach where we keep subtracting the divisor from the dividend and count how many times we can do this until the dividend is less than the divisor. This is a valid first step but not efficient enough for large numbers, which is where bit manipulation comes in handy.
To improve efficiency, instead of subtracting the divisor once at a time, we exponentially increase the subtracted amount by left shifting the divisor (which is equivalent to multiplying by powers of 2) and subtract this from the dividend if possible. This approach is much faster, as left shifting effectively doubles the subtracted amount each time, allowing us to subtract large chunks in logarithmic time compared to a linear approach.
The whole process loops, increasing the amount being subtracted each time (as long as the double of the current subtraction amount is still less than or equal to the remaining dividend) and adding the corresponding power of 2 to our total. This loop represents a divide and conquer strategy that works through the problem using bit-level operations to mimic standard division while ensuring the result stays within the specified integer range.
Time and space complexity is considered, especially since we are working within a constrained environment that doesn't allow typical operations. The time complexity here is O(log(a) * log(b)), with 'a' being the dividend and 'b' the divisor. This complexity arises because the algorithm processes parts of the dividend in a time proportional to the logarithm of its size, and likewise for the divisor since the subtraction step is proportional to its logarithm as well. The space complexity is constant, O(1), since we use a fixed number of variables regardless of the size of the inputs.
Learn more about Math patterns.
Solution Approach
The approach to solving the division problem without multiplication, division, or mod operator involves a few key steps and utilizes simple yet powerful concepts of bit manipulation to efficiently find the quotient.
Here's a step-by-step walkthrough of the implementation:
-
Handle Signs:
- First, we need to handle the sign of the quotient. If the
dividend
anddivisor
have the same sign, the result is positive; otherwise, it's negative. We define the variablesign
and use a simple comparison to set its value to-1
for a negative result or1
for a positive one. - The actual division operation will be conducted on the absolute values of the
dividend
anddivisor
.
- First, we need to handle the sign of the quotient. If the
-
Initialize Variables:
- Set
INT_MAX
as(1 << 31) - 1
, which represents the maximum positive value for a 32-bit integer. - Set
INT_MIN
as-(1 << 31)
, representing the minimum negative value for a 32-bit integer. - Initialize the quotient
tot
to0
.
- Set
-
Bitwise Shift for Division:
- We start a loop where we continue to subtract the
divisor
from thedividend
untildividend
is smaller thandivisor
. For each subtraction:- Initialize a counter
cnt
with0
. - Inside an inner loop, left shift the
divisor
bycnt + 1
positions, effectively multiplying thedivisor
by2
each time, until it would exceed the currentdividend
. - After finding the maximum amount by which we can multiply the
divisor
without exceeding thedividend
, we add1 << cnt
to our running totaltot
. This is equivalent to adding2^cnt
. - Reduce the
dividend
bydivisor << cnt
.
- Initialize a counter
- We start a loop where we continue to subtract the
-
Finalizing Result:
- Multiply the
tot
by thesign
to apply the correct sign to the result. - Handle potential integer overflow by comparing the result against
INT_MAX
andINT_MIN
:- If the result is within the range
[INT_MIN, INT_MAX]
, return the result. - If the result exceeds the range, return
INT_MAX
.
- If the result is within the range
- Multiply the
This algorithm effectively simulates division by breaking it down into a combination of subtraction and left bitwise shift operations, replicating multiplication by powers of 2. It's a logarithmic solution in the sense that it reduces the problem size by approximately half with each recursive subtraction, hence the O(log a * log b)
time complexity, where a
is the dividend and b
is the divisor. Space complexity is O(1)
since the number of variables used does not scale with input size.
The pattern used here can be thought of as a "divide and conquer" as well as "bit manipulation". By using these principles, we can efficiently and accurately divide two integers in a constrained environment.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach as described. Suppose our dividend
is 10 and our divisor
is 3. We need to find out how many times we can subtract 3 from 10, with the operations restricted as per the problem statement.
1. Handle Signs:
- Both the
dividend
(10) anddivisor
(3) are positive, so our result will also be positive. Thus,sign = 1
.
2. Initialize Variables:
INT_MAX
is set as(1 << 31) - 1
andINT_MIN
is set as-(1 << 31)
.- Initialize total quotient
tot = 0
.
3. Bitwise Shift for Division:
- Begin the loop to subtract
divisor
fromdividend
.- On the first iteration,
cnt = 0
. We check if(divisor << cnt + 1) <= dividend
:3 << 0
is3
, and3 << 1
(which is6
) is still<= 10 (dividend)
.3 << 2
would be12
, which exceeds10
. So, we can stop atcnt = 1
.
- Add
1 << cnt
which is1 << 1
or2
totot
. - Subtract
divisor << cnt
which is3 << 1
or6
fromdividend
. Now,dividend = 10 - 6 = 4
.
- On the first iteration,
- With the new
dividend
of 4, repeat the process:- On the second iteration,
cnt = 0
.3 << cnt + 1
is6
, which is greater than4
. So we can't shiftcnt
to 1 this time. - Add
1 << cnt
which is1
totot
. Now,tot = 2 + 1 = 3
. - Subtract
divisor << cnt
(which is3
) fromdividend
. Now,dividend = 4 - 3 = 1
.
- On the second iteration,
4. Finalizing Result:
- Because
dividend
is now less thandivisor
, we can conclude our calculation. - Since we began with
tot = 0
and added2
first and then1
to it, we havetot = 3
. - Multiply
tot
bysign
. Sincesign = 1
, the result remainstot = 3
. - Check for overflow, which isn't the case here, so the final result is
3
.
Thus, dividing 10 by 3 yields a quotient of 3
using this approach. Since we are only concerned with the integer part of the division, the remainder is disregarded, aligning with the truncation towards zero rule. The bit manipulation significantly speeds up the process by allowing us to subtract larger powers of 2 wherever possible.
Solution Implementation
1class Solution:
2 def divide(self, dividend: int, divisor: int) -> int:
3 # Define the boundaries for an integer (32-bit signed integer)
4 INT_MAX = 2**31 - 1
5 INT_MIN = -2**31
6
7 # Determine the sign of the output. If dividend and divisor have different signs, result will be negative
8 sign = -1 if (dividend * divisor) < 0 else 1
9
10 # Work with positive values for both dividend and divisor
11 dividend = abs(dividend)
12 divisor = abs(divisor)
13
14 # Initialize the total quotient
15 total_quotient = 0
16
17 # Loop to find how many times the divisor can fit into the dividend
18 while dividend >= divisor:
19 # Count will keep track of the number of times we can double the divisor while still being less than or equal to dividend
20 count = 0
21 # Double the divisor as much as possible without exceeding the dividend
22 while dividend >= (divisor << (count + 1)):
23 count += 1
24 # Increment total_quotient by the number of times we doubled the divisor
25 total_quotient += 1 << count
26 # Decrease dividend by the matched part which we just calculated
27 dividend -= divisor << count
28
29 # Multiply the result by the sign
30 result = sign * total_quotient
31
32 # Check and correct for overflow: if result is out of the 32-bit signed integer range, clamp it to INT_MAX
33 if result < INT_MIN:
34 return INT_MIN
35 elif result > INT_MAX:
36 return INT_MAX
37 else:
38 return result
39
1class Solution {
2 public int divide(int dividend, int divisor) {
3 // Determine the sign of the result
4 int sign = 1;
5 if ((dividend < 0) != (divisor < 0)) {
6 sign = -1;
7 }
8
9 // Use long to avoid integer overflow issues
10 long longDividend = Math.abs((long) dividend);
11 long longDivisor = Math.abs((long) divisor);
12
13 // This will accumulate the result of the division
14 long total = 0;
15
16 // Loop to find how many times the divisor can be subtracted from the dividend
17 while (longDividend >= longDivisor) {
18 // This counter will keep track of the number of left shifts
19 int count = 0;
20
21 // Double the divisor until it is less than or equal to the dividend
22 while (longDividend >= (longDivisor << (count + 1))) {
23 count++;
24 }
25
26 // Add the number of times we could double the divisor to the total
27 total += 1L << count;
28
29 // Subtract the final doubled divisor value from the dividend
30 longDividend -= longDivisor << count;
31 }
32
33 // Multiply the sign back into the total
34 long result = sign * total;
35
36 // Handle overflow cases by clamping to the Integer range
37 if (result >= Integer.MIN_VALUE && result <= Integer.MAX_VALUE) {
38 return (int) result;
39 }
40
41 // If the result is still outside the range, return the max integer value
42 return Integer.MAX_VALUE;
43 }
44}
45
1class Solution {
2public:
3 int divide(int dividend, int divisor) {
4 // Determine sign of the result based on the signs of dividend and divisor
5 int resultSign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
6
7 // Use long long to avoid overflow issues for abs(INT32_MIN)
8 long long absDividend = abs(static_cast<long long>(dividend));
9 long long absDivisor = abs(static_cast<long long>(divisor));
10 long long result = 0; // Initialize result
11
12 // Loop until the dividend is smaller than divisor
13 while (absDividend >= absDivisor) {
14 int shiftCount = 0; // Count how many times the divisor has been left-shifted
15
16 // Find the largest shift where the shifted divisor is smaller than or equal to dividend
17 while (absDividend >= (absDivisor << (shiftCount + 1))) {
18 ++shiftCount;
19 }
20
21 // Add to the result the number represented by the bit at the found position
22 result += 1ll << shiftCount;
23
24 // Reduce dividend by the found multiple of divisor
25 absDividend -= absDivisor << shiftCount;
26 }
27
28 // Apply sign of result
29 result *= resultSign;
30
31 // Handle overflow by returning INT32_MAX if the result is not within int range
32 if (result >= INT32_MIN && result <= INT32_MAX) {
33 return static_cast<int>(result);
34 }
35 return INT32_MAX;
36 }
37};
38
1// Global function for division without using division operator
2function divide(dividend: number, divisor: number): number {
3 // Determine sign of the result based on the signs of dividend and divisor
4 let resultSign: number = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
5
6 // Use number to accommodate for JavaScript's safe integer range
7 // and to avoid precision issues with bitwise operations
8 let absDividend: number = Math.abs(dividend);
9 let absDivisor: number = Math.abs(divisor);
10 let result: number = 0; // Initialize result
11
12 // Loop until the dividend is smaller than divisor
13 while (absDividend >= absDivisor) {
14 let shiftCount: number = 0; // Count how many times the divisor has been multiplied by 2
15
16 // Find the largest multiple of 2 for divisor that is still less than or equal to dividend
17 while (absDividend >= (absDivisor * Math.pow(2, shiftCount + 1))) {
18 shiftCount++;
19 }
20
21 // Accumulate the quotient by the power of 2 corresponding to the shift count
22 result += Math.pow(2, shiftCount);
23
24 // Decrease dividend by the found multiple of the divisor
25 absDividend -= absDivisor * Math.pow(2, shiftCount);
26 }
27
28 // Apply the sign of the result
29 result *= resultSign;
30
31 // Handle overflow by returning the maximum safe integer value if the result is not within 32-bit signed integer range
32 if (result >= -(2 ** 31) && result <= (2 ** 31) - 1) {
33 return Math.trunc(result);
34 }
35 return (2 ** 31) - 1;
36}
37
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(log(a) * log(b))
. This is because in the first while
loop, we're checking if a
is greater than or equal to b
, which requires O(log(a))
time since in each iteration a
is reduced roughly by a factor of two or more. The inner while
loop is responsible for finding the largest shift of b
that a
can handle, which will execute at most O(log(b))
times, as shifting b
left by one doubles its value, and cnt
increases until a
is no longer greater than b
shifted by cnt + 1
. Therefore, these two loops combined yield the time complexity mentioned.
Space Complexity
The space complexity of the given code is O(1)
. Only a fixed number of integer variables sign
, tot
, and cnt
are used, which do not depend on the size of the input. Hence, the space used is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.