LeetCode: 29. Divide Two Integers

LeetCode: 29. Divide Two Integers

Problem: 29. Divide Two Integers

Link: https://leetcode.com/problems/divide-two-integers/

Difficulty: Medium

Description:

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹ − 1]. For the purpose of this problem, assume that your function returns 2³¹ − 1 when the division result overflows.

Solution:

Language: Swift

Runtime: 12ms
Memory: 18.5MB

Copy to Clipboard

class Solution {
    func divide(_ dividend: Int, _ divisor: Int) -> Int {
        if dividend == 0 {
            return 0
        }
        if divisor == 1 {
            return dividend
        }
        
        let isNegative = !((dividend > 0) == (divisor > 0))
        
        var dividend = abs(dividend)
        var divisor = abs(divisor)
        var result = 0
        
        while dividend >= divisor {
            var multiplier = 1
            var temp = divisor
            
            //divided by 2 as many as possible
            while dividend >= (temp << 1) {
                temp <<= 1
                multiplier <<= 1
            }
            
            //calculate the remaining number
            dividend -= temp
            result += multiplier
        }
        
        var ans = isNegative ? -result : result
        
        if ans > Int32.max {
            return Int(Int32.max)
        }
        if ans < Int32.min {
            return Int(Int32.min)
        }
        
        return ans
    }
}

Related Posts

Leave A Comment Cancel reply