How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Amazon during technical interviews.

Implement integer division without using division

Company: Amazon

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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):** ```text int divide(int dividend, int divisor); ``` Explain the algorithm you would use and then implement the function in the programming language of your choice.

Quick Answer: 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.

Given two 32-bit signed integers dividend and divisor, implement integer division and return the integer quotient. You may not use the multiplication (*), division (/), or modulo (%) operators. The quotient must be truncated toward zero. If the result would overflow the 32-bit signed integer range, return 2^31 - 1.

Constraints

-2^31 <= dividend <= 2^31 - 1
-2^31 <= divisor <= 2^31 - 1
divisor != 0
Do not use multiplication (*), division (/), or modulo (%) operators
The algorithm should be better than O(|dividend|)

Examples

Input: (10, 3)

Expected Output: 3

Explanation: 10 divided by 3 is 3.333..., which truncates toward zero to 3.

Input: (7, -3)

Expected Output: -2

Explanation: 7 divided by -3 is -2.333..., which truncates toward zero to -2.

Input: (-15, 4)

Expected Output: -3

Explanation: -15 divided by 4 is -3.75, which truncates toward zero to -3.

Input: (0, 5)

Expected Output: 0

Explanation: Zero divided by any nonzero integer is 0.

Input: (-2147483648, -1)

Expected Output: 2147483647

Explanation: The mathematical result is 2147483648, which exceeds the maximum 32-bit signed integer, so the result is clamped to 2147483647.

Input: (-2147483648, 1)

Expected Output: -2147483648

Explanation: The quotient is exactly the minimum 32-bit signed integer, so it is returned unchanged.

Solution

def solution(dividend, divisor):
    INT_MIN = -(1 << 31)
    INT_MAX = (1 << 31) - 1

    # The only overflow case for 32-bit signed integer division.
    if dividend == INT_MIN and divisor == -1:
        return INT_MAX

    # Determine whether the final result should be negative.
    negative = (dividend < 0) != (divisor < 0)

    # Work with positive magnitudes. Python can safely represent abs(INT_MIN).
    a = -dividend if dividend < 0 else dividend
    b = -divisor if divisor < 0 else divisor

    quotient = 0

    # Build the quotient from high powers of two down to low powers of two.
    # Since inputs are 32-bit, checking shifts from 31 down to 0 is enough.
    for shift in range(31, -1, -1):
        shifted = b << shift
        if shifted <= a:
            a -= shifted
            quotient += 1 << shift

    if negative:
        quotient = -quotient

    if quotient < INT_MIN:
        return INT_MIN
    if quotient > INT_MAX:
        return INT_MAX
    return quotient

Time complexity: O(log |dividend|), which is at most 32 iterations for 32-bit integers. Space complexity: O(1).

Hints

Instead of subtracting the divisor one time at a time, try subtracting the largest doubled version of the divisor that fits into the remaining dividend.
Bit shifts can be used to efficiently double numbers and build the quotient from powers of two.

Quick Overview

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.