Katkat
Back

Implement integer division without using division

AmazonApplied Scientist · Onsite
MediumApplied ScientistOnsiteCoding & Algorithms

Last updated

This question evaluates proficiency in implementing low-level integer arithmetic and algorithmic optimization, including correct handling of overflow and edge cases within 32-bit signed integer constraints.

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):

int divide(int dividend, int divisor);

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