/
Medium_029_Divide_Two_Integers.swift
51 lines (42 loc) · 1.38 KB
/
Medium_029_Divide_Two_Integers.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
https://leetcode.com/problems/divide-two-integers/
#29 Divide Two Integers
Level: meidum
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Inspired by @lucastan & @ngcl at https://leetcode.com/discuss/11358/simple-o-log-n-2-c-solution
*/
import Foundation
struct Medium_029_Divide_Two_Integers {
static func divide(dividend: Int, divisor: Int) -> Int {
if divisor == 0 {
return Int.max
}
if divisor == 1 {
return dividend
}
if dividend == Int.min && divisor == Int.min {
return 1
}
if dividend == Int.min && abs(divisor) == 1 {
return Int.max
}
var answer: UInt = 0
var absDividend: UInt = dividend == Int.min ? UInt(UInt(Int.max) + 1) : UInt(abs(dividend))
let absDivisor: UInt = divisor == Int.min ? UInt(UInt(Int.max) + 1) : UInt(abs(divisor))
while absDividend >= absDivisor {
var tmp: UInt = UInt(absDivisor)
var power: UInt = 1
while tmp << 1 < absDividend {
tmp <<= 1
power <<= 1
}
answer += power
absDividend -= tmp
}
if (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) {
return 0 - Int(answer)
}
return Int(answer)
}
}