Skip to main content

Leetcode 29: Divide Two Integers

 

1. Problem Statement (Simple Explanation):


You are given two integers:

  • dividend

  • divisor (non-zero)

You must compute:


Subject to:

  • You cannot use:

    • multiplication (*)

    • division (/)

    • modulo (%)

  • You must handle 32-bit signed integer range:

[-231,231-1]=[-2147483648,2147483647]

  • If the quotient is strictly greater than 231 - 1, return 231 - 1.

  • If the quotient is strictly less than -231, return -231.

Truncation toward zero means:

  • 8 / 3 = 2.66... → 2

  • -8 / 3 = -2.66... → -2


2. Examples:


Example 1:

Input: dividend = 10, divisor = 3

Exact division: 10 / 3 ≈ 3.3333 → truncated toward zero → 3.

Output: 3


Example 2:

Input: dividend = 7, divisor = -3

Exact division: 7 / -3 ≈ -2.3333 → truncated toward zero → -2.

Output: -2


Constraints:


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

  • divisor != 0


3. Approach 1 – Naive Repeated Subtraction (Too Slow):


Conceptually:

  • Repeatedly subtract divisor from dividend and count how many times until remainder becomes smaller than divisor.

Problems:

  • If |dividend| and |divisor| are large (e.g., 109), this is O(|quotient|) → too slow.

We need something faster, ideally O(log(|dividend|).


4. Approach 2 – Bitwise Doubling (Fast, Like Binary Long Division):


We can simulate division using bit shifts and subtractions, similar to long division.


Ideas:


  1. Work with absolute values to simplify, then apply the sign at the end.

  2. Use bit shifting to subtract large multiples of divisor at once:

    • Instead of subtracting divisor one by one, find the largest multiple = divisor * 2k such that multiple <= dividend.

    • Subtract this multiple and add 2k to the quotient.

  3. Repeat until the remaining dividend is smaller than divisor.

Since we can’t use *, we can generate divisor * 2k via divisor << k (left shift).

To avoid overflow issues, it's common to work in the negative domain (since range of negative integers is slightly larger: INT_MIN = -2147483648).


Handling Signs and Overflow:


Let:

  • INT_MAX = 2147483647

  • INT_MIN = -2147483648

Special overflow case:

  • dividend = INT_MIN, divisor = -1 → exact result is 2147483648, which is out of 32-bit signed range.

  • In this case, return INT_MAX.

Sign:

  • negative = (dividend < 0) XOR (divisor < 0)

  • Work with negative numbers to avoid overflow when negating INT_MIN.

We convert both to negative:

  • dvd = (dividend > 0) ? -dividend : dividend

  • dvs = (divisor > 0) ? -divisor : divisor

Then both dvd and dvs are ≤ 0.


Core Loop (Negative Domain):


We want to compute:

quotient=⌊dvd/dvs⌋

But both are negative, so dvd <= dvs <= 0 and the quotient will be positive or negative depending on signs.

Outline:



After finishing, if negative is true, result is -quotient, else quotient.


Pseudo-code (Bitwise Doubling, Negative Domain):



Complexity:


Let D = |dividend|:

  • Outer loop: each iteration subtracts at least half of current dvd (in magnitude).

  • Inner loop: finds largest power-of-two multiple via shifts (logarithmic).

Total time: O(logD)

Space: O(1)


5. Java code:



6. C code:



7. C++ code:



8. Python code:



9. JavaScript code:



JavaScript numbers are 64-bit floating, but bitwise operations treat them as 32-bit signed ints, which we can leverage.


Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more