Implement integer division without using division

Q: Implement integer division without using division

This is a Coding & Algorithms interview question from Amazon for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given two 32-bit signed integers dividend and divisor.

Implement a function that divides dividend by divisor and returns the integer quotient, without using the multiplication *, division /, or modulo % operators.

The result should be truncated toward zero (i.e., rounded toward 0, not toward −∞ or +∞).

Assume:

divisor is not zero.
The range of 32-bit signed integers is from −2³¹ to 2³¹ − 1.

You must:

Handle potential overflow correctly. If the result overflows the 32-bit signed integer range, return 2^31 - 1 (the maximum 32-bit signed integer).
Aim for a time complexity better than O(|dividend|) (i.e., you should not subtract divisor from dividend one unit at a time).

Function signature example (language-agnostic):

Explain the algorithm you would use and then implement the function in the programming language of your choice.

Implement integer division without using division

Comments (0)