LeetCode解説　一日一問　29. Divide Two Integers

LeetCodeって？
問題
回答
1. 解法
2. 別解
コード
結果

LeetCodeって？

Just a moment...

LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。

2022年12月現在2,000問を超える問題が登録されています。

各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。

正誤判定は自動で行われます。

使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。

私はPython3で解いています。

Pythonではじめるアルゴリズム入門伝統的なアルゴリズムで学ぶ定石と計算量 [ 増井敏克 ]

問題

Just a moment...

タイトル：29. Divide Two Integers

難易度：Medium

内容：

2つの整数 dividend と divisor が与えられる。

dividend / divisor の小数点以下を取り除いた整数を返す。

ただし、返り値の範囲は[−2³¹, 2³¹ − 1]とする。

例：

Input: dividend = 10, divisor = 3
Output: 3
※10 / 3 = 3.333...　小数点以下を除いて3

Input: dividend = 7, divisor = -3
Output: -2
7 / -2 = -2.333...　小数点以下を除いて-2

回答

いわゆるゼロ方向への丸めです。

解法

decimalモジュールを使うといろいろな丸めを簡単に実装できます。

1行で実装できます。

return max(min(int(Decimal(dividend / divisor).quantize(Decimal('1'), rounding=ROUND_DOWN)),2**31-1), -2**31)

decimalモジュールを使った丸めの詳細については以下のページで紹介されています。

Pythonの丸め処理について調べてみた | DevelopersIO

別解

せっかくなので別の解法も考えてみます。

解が負の値の場合切り捨て除算 // をしてしまうと、負の無限大方向に丸められてしまいます。

なので、dividend と divisor の絶対値をとり切り捨て除算を行った後、解が負になるようであれば負の数にする方法です。

sign = np.sign(np.sign(dividend) * np.sign(divisor))
ans = abs(dividend) // abs(divisor)
if sign < 0:
    ans = -ans
return max(min(ans, 2**31-1),-2**31)

コード

コード全文です。

from decimal import Decimal, ROUND_DOWN
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        return int(Decimal(dividend / divisor).quantize(Decimal('1'), rounding=ROUND_DOWN))

コードはgithubにも保管しています。