-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathm0029.py
67 lines (51 loc) · 1.62 KB
/
m0029.py
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
"""Divide Two Integers
TAG: binary-search, math
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: [−231, 231 − 1]. For the purpose of this
problem, assume that your function returns 231 − 1 when the division result
overflows.
"""
from __future__ import annotations
from typing import Any, Optional
class Bisection(object):
@staticmethod
def solution(dividend, divisor):
def helper(dividend_, divisor_):
res_ = 0
i_ = 1
_dividend_ = dividend_
_divisor_ = divisor_
while True:
if _dividend_ < _divisor_:
break
_dividend_ -= _divisor_
_divisor_ += _divisor_
res_ += i_
i_ += i_
return res_, _dividend_
rec = 0
dividend__ = dividend
while True:
res, dividend__ = helper(dividend__, divisor)
if res == 0:
break
rec += res
return rec
if __name__ == '__main__':
input_1_1 = 113
input_1_2 = 3
exp_1 = 37
assert Bisection.solution(input_1_1, input_1_2) == exp_1